2015/03/23 by Christoph Lenzen, Lenzen, Christoph, Joel Rybicki +3
Computer Science · Engineering · #Distributed systems and fault tolerance #Interconnection Networks and Systems #Advanced Memory and Neural Computing
paper · pdf · doi:10.48550/arxiv.1503.06702
Consider a complete communication network of n nodes, where 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 counting modulo c in agreement. Thus, we are considering algorithms that are self-stabilizing 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 space complexity of deterministic algorithms, while still achieving linear stabilisation time and almost-linear resilience.