Abstract | ||
---|---|---|
Consider a fully-connected synchronous distributed system consisting of n nodes, where up to f nodes may be faulty and every node starts in an arbitrary initial state. In the synchronous C-counting problem, all nodes need to eventually agree on a counter that is increased by one modulo C in each round for given \(C>1\). In the self-stabilising firing squad problem, the task is to eventually guarantee that all non-faulty nodes have simultaneous responses to external inputs: if a subset of the correct nodes receive an external “go” signal as input, then all correct nodes should agree on a round (in the not-too-distant future) in which to jointly output a “fire” signal. Moreover, no node should generate a “fire” signal without some correct node having previously received a “go” signal as input. We present a framework reducing both tasks to binary consensus at very small cost. For example, we obtain a deterministic algorithm for self-stabilising Byzantine firing squads with optimal resilience \(f<n/3\), asymptotically optimal stabilisation and response time O(f), and message size \(O(\log f)\). As our framework does not restrict the type of consensus routines used, we also obtain efficient randomised solutions. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1007/978-3-319-49259-9_21 | SSS |
Keywords | DocType | Volume |
Byzantine faults, Self-stabilisation, Clock synchronisation, Synchronous counting, Firing squads | Conference | abs/1608.00214 |
ISSN | Citations | PageRank |
0302-9743 | 1 | 0.36 |
References | Authors | |
18 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Christoph Lenzen | 1 | 584 | 40.61 |
Joel Rybicki | 2 | 78 | 9.69 |