Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Synchronous Counting and Computational Algorithm Design
verfasst von : Danny Dolev, Janne H. Korhonen, Christoph Lenzen, Joel Rybicki, Jukka Suomela
Erschienen in: Stabilization, Safety, and Security of Distributed Systems
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.