Christoph Lenzen · Joel Rybicki · Jukka Suomela

Towards optimal synchronous counting

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

authors’ version publisher’s version arXiv.org

Abstract

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.

Publication

Chryssis Georgiou and Paul G. Spirakis (Eds.): PODC’14, 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

Journal Version

© ACM 2015 — This is the authors’ version of the work. It is posted here for your personal use. Not for redistribution. The definitive version was published in Proc. PODC 2015.

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.