Danny Dolev · Janne H. Korhonen · Christoph Lenzen · Joel Rybicki · Jukka Suomela

Synchronous counting and computational algorithm design

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

authors’ version publisher’s version arXiv.org


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


Journal Version

© Springer 2013 — The original publication is available at www.springerlink.com.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.