Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Towards Optimal Synchronous Counting


Lenzen,  Christoph
Algorithms and Complexity, MPI for Informatics, Max Planck Society;


Rybicki,  Joel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 530KB

Supplementary Material (public)
There is no public supplementary material available

Lenzen, C., Rybicki, J., & Suomela, J. (2015). Towards Optimal Synchronous Counting. Retrieved from http://arxiv.org/abs/1503.06702.

Cite as: https://hdl.handle.net/11858/00-001M-0000-002A-07C2-2
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.