PODC 2015 · 34th Annual ACM Symposium on Principles of Distributed Computing, Donostia-San Sebastián, Spain, July 2015 · doi:10.1145/2767386.2767423

Consider a complete communication network of $n$ nodes, in which 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 count modulo $c$ in agreement. Thus, we are considering algorithms that are self-stabilising 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 state complexity of deterministic algorithms, while still achieving linear stabilisation time and almost-linear resilience.

Chryssis Georgiou and Paul G. Spirakis (Eds.): *PODC’15, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, July 21–23, 2015, Donostia–San Sebastián, Spain*, pages 441–450, ACM Press, New York, 2015

ISBN 978-1-4503-3617-8

- Christoph Lenzen, Joel Rybicki, and Jukka Suomela: Efficient counting with optimal resilience ·
*SIAM Journal on Computing*46:1473–1500, 2017