hide
Free keywords:
Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC
Abstract:
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.
