SSS 2013 · 15th International Symposium on Stabilization, Safety, and Security of Distributed Systems, Osaka, Japan, November 2013 · doi:10.1007/978-3-319-03089-0_17
Consider a complete communication network on n nodes, each of which is a state machine with s states. In synchronous 2-counting, the nodes receive a common clock pulse and they have to agree on which pulses are “odd” and which are “even”. We require that the solution is self-stabilising (reaching the correct operation from any initial state) and it tolerates f Byzantine failures (nodes that send arbitrary misinformation). Prior algorithms are expensive to implement in hardware: they require a source of random bits or a large number of states s. We use computational techniques to construct very compact deterministic algorithms for the first non-trivial case of f = 1. While no algorithm exists for n < 4, we show that as few as 3 states are sufficient for all values n ≥ 4. We prove that the problem cannot be solved with only 2 states for n = 4, but there is a 2-state solution for all values n ≥ 6.
Teruo Higashino, Yoshiaki Katayama, Toshimitsu Masuzawa, Maria Potop-Butucaru, and Masafumi Yamashita (Eds.): Stabilization, Safety, and Security of Distributed Systems, 15th International Symposium, SSS 2013, Osaka, Japan, November 13–16, 2013, Proceedings, volume 8255 of Lecture Notes in Computer Science, pages 237–250, Springer, Berlin, 2013
ISBN 978-3-319-03088-3