Towards optimal synchronous counting

DOI10.1145/2767386.2767423MaRDI QIDQ2796281zbMATH OpenOpenAlexFDO

Authors Christoph Lenzen, Joel Rybicki, Jukka Suomela

Publication date 23 March 2016

Published in Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

Byzantine fault-toleranceself-stabilisationsynchronous counting

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15) Distributed systems (68M14)

Abstract: Consider a complete communication network of $n$ nodes, where the nodes receive a common clock pulse. We study the synchronous $c$-counting problem: given any starting state and up to $f$ faulty nodes with arbitrary behaviour, the task is to eventually have all correct nodes counting modulo $c$ in agreement. Thus, we are considering algorithms that are self-stabilizing despite Byzantine failures. In this work, we give new algorithms for the synchronous counting problem that (1) are deterministic, (2) have linear stabilisation time in $f$, (3) use a small number of states, and (4) achieve almost-optimal resilience. Prior algorithms either resort to randomisation, use a large number of states, or have poor resilience. In particular, we achieve an exponential improvement in the space complexity of deterministic algorithms, while still achieving linear stabilisation time and almost-linear resilience.

Recommendations

• Synchronous counting and computational algorithm design
• Concurrent counting (extended abstract)
• Efficient counting with optimal resilience
• Efficient counting with optimal resilience
• Abstracting and counting synchronizing processes
• An inherent bottleneck in distributed counting
• Time and space optimal counting in population protocols
• Concurrent counting

Cites work

• scientific article; zbMATH DE number 826255 (Why is no real title available?)
• Memorization and Association on a Realistic Neural Model

Cited in

(11)

• Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits
• An efficient counting network
• Efficient counting with optimal resilience
• Timing conditions for linearizability in uniform counting networks
• Efficient counting with optimal resilience
• Concurrent counting is harder than queuing
• An inherent bottleneck in distributed counting
• Synchronous counting and computational algorithm design
• Near-optimal self-stabilising counting and firing squads
• Near-optimal self-stabilising counting and firing squads
• Concurrent counting

This page was built for publication: Towards optimal synchronous counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2796281)