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