Gradient clock synchronization in dynamic networks

DOI10.1007/s00224-011-9348-1zbMath1253.68060OpenAlexW2039856994MaRDI QIDQ693764

Fabian Kuhn, Rotem Oshman, Thomas Locher

Publication date: 10 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1721.1/45549

zbMATH Keywords

lower bounddistributed algorithmsdynamic networksgradient clock synchronization

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (35)

Coordinated consensus in dynamic networks ⋮ Error-free multi-valued consensus with byzantine failures ⋮ Distributed graph coloring in a few rounds ⋮ MIS on trees ⋮ Toward more localized local algorithms ⋮ The complexity of robust atomic storage ⋮ Resilience of mutual exclusion algorithms to transient memory faults ⋮ The impact of memory models on software reliability in multiprocessors ⋮ A complexity separation between the cache-coherent and distributed shared memory models ⋮ From bounded to unbounded concurrency objects and back ⋮ The space complexity of long-lived and one-shot timestamp implementations ⋮ Locally checkable proofs ⋮ Fault-tolerant spanners ⋮ Adaptively secure broadcast, revisited ⋮ Scalable rational secret sharing ⋮ Analyzing consistency properties for fun and profit ⋮ Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions ⋮ Optimal-time adaptive strong renaming, with applications to counting ⋮ The round complexity of distributed sorting ⋮ A tight unconditional lower bound on distributed randomwalk computation ⋮ Minimum congestion mapping in a cloud ⋮ Conflict on a communication channel ⋮ Stability of a peer-to-peer communication system ⋮ Tight bounds on information dissemination in sparse mobile networks ⋮ Time-efficient randomized multiple-message broadcast in radio networks ⋮ Faster information dissemination in dynamic networks via network coding ⋮ Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony ⋮ Brief Announcement: Efficient Computation in Congested Anonymous Dynamic Networks ⋮ Order optimal information spreading using algebraic gossip ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ Structuring unreliable radio networks ⋮ Byzantine agreement with homonyms ⋮ Distributed deterministic edge coloring using bounded neighborhood independence ⋮ Compact policy routing ⋮ Xheal

Cites Work

• Unnamed Item
• On the possibility and impossibility of achieving clock synchronization
• Closed form bounds for clock synchronization under simple uncertainty assumptions
• Gradient clock synchronization
• A theory of clock synchronization (extended abstract)
• Optimal and efficient clock synchronization under drifting clocks
• The Theory of Timed I/O Automata, Second Edition
• Oblivious Gradient Clock Synchronization
• An upper and lower bound for clock synchronization
• Synchronizing clocks in the presence of faults
• Dynamic fault-tolerant clock synchronization
• Optimal Clock Synchronization under Different Delay Assumptions
• Tight bounds for clock synchronization
• Optimal gradient clock synchronization in dynamic networks
• Principles of Distributed Systems

This page was built for publication: Gradient clock synchronization in dynamic networks