Optimal gradient clock synchronization in dynamic networks

DOI10.1145/1835698.1835799zbMath1315.68009arXiv1005.2894OpenAlexW2132763546MaRDI QIDQ5176218

Thomas Locher, Fabian Kuhn, Rotem Oshman, Christoph Lenzen

Publication date: 2 March 2015

Published in: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1005.2894

zbMATH Keywords

dynamic networksclock synchronization

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (36)

Clock Synchronization and Estimation in Highly Dynamic Networks: An Information Theoretic Approach ⋮ 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 ⋮ Order optimal information spreading using algebraic gossip ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ Gradient clock synchronization in dynamic networks ⋮ Structuring unreliable radio networks ⋮ Byzantine agreement with homonyms ⋮ Distributed deterministic edge coloring using bounded neighborhood independence ⋮ Compact policy routing ⋮ Fault-tolerant algorithms for tick-generation in asynchronous logic ⋮ Xheal

Uses Software

• CCSTM

Cites Work

• Elastic Transactions
• Toward a theory of transactional contention managers
• Software transactional memory

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