Name
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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1145/2767386.2767423 | ACM Symposium on Principles of Distributed Computing |
Keywords | Field | DocType |
synchronous counting, self-stabilisation, Byzantine fault-tolerance | Small number,Clock signal,Psychological resilience,Telecommunications network,Exponential function,Modulo,Computer science,Byzantine fault tolerance,Counting problem,Theoretical computer science,Distributed computing | Journal |
Volume | Citations | PageRank |
abs/1503.06702 | 4 | 0.41 |
References | Authors | |
11 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Lenzen | 1 | 584 | 40.61 |
| Joel Rybicki | 2 | 78 | 9.69 |
| Jukka Suomela | 3 | 600 | 46.99 |