English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Towards Optimal Synchronous Counting

MPS-Authors
/persons/resource/persons123371

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

/persons/resource/persons135714

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)

arXiv:1503.06702.pdf
(Preprint), 530KB

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

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
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.