Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-319-03089-0_17 | J. Comput. Syst. Sci. |
DocType | Volume | Issue |
Journal | 82 | 2 |
ISSN | Citations | PageRank |
0022-0000 | 1 | 0.37 |
References | Authors | |
14 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Danny Dolev | 1 | 6925 | 1305.43 |
| Janne Korhonen | 2 | 71 | 10.52 |
| Christoph Lenzen | 3 | 584 | 40.61 |
| Joel Rybicki | 4 | 78 | 9.69 |
| Jukka Suomela | 5 | 600 | 46.99 |