Synchronous Counting
Loading...
Restricted Availability
Date
Persistent identifier of the Data Catalogue metadata
Creator/contributor
Editor
Journal title
Journal volume
Publisher
Publication Type
software
software
software
Peer Review Status
Repositories
Access rights
Open
Cite this resource
Dolev, D., Korhonen, J. H., Lenzen, C., Rybicki, J., & Suomela, J. (2013). Synchronous Counting. Zenodo. https://doi.org/10.5281/ZENODO.9816
ISBN
ISSN
Description
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.
This repository contains:
computer-generated algorithms,
computer-generated lower-bound proofs,
Python scripts that can be used to verify that the algorithms and the lower-bound proofs are correct,
additional illustrations.
For more information, see:
doi:10.1007/978-3-319-03089-0_17
arXiv:1304.5719