hide
Free keywords:
Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC
Abstract:
In the synchronous $c$-counting problem, we are given a synchronous system of
$n$ nodes, where up to $f$ of the nodes may be Byzantine, that is, have
arbitrary faulty behaviour. The task is to have all of the correct nodes count
modulo $c$ in unison in a self-stabilising manner: regardless of the initial
state of the system and the faulty nodes' behavior, eventually rounds are
consistently labelled by a counter modulo $c$ at all correct nodes.
We provide a deterministic solution with resilience $f<n/3$ that stabilises
in $O(f)$ rounds and every correct node broadcasts $O(\log^2 f)$ bits per
round. We build and improve on a recent result offering stabilisation time
$O(f)$ and communication complexity $O(\log^2 f /\log \log f)$ but with
sub-optimal resilience $f = n^{1-o(1)}$ (PODC 2015). Our new algorithm has
optimal resilience, asymptotically optimal stabilisation time, and low
communication complexity.
Finally, we modify the algorithm to guarantee that after stabilisation very
little communication occurs. In particular, for optimal resilience and
polynomial counter size $c=n^{O(1)}$, the algorithm broadcasts only $O(1)$ bits
per node every $\Theta(n)$ rounds without affecting the other properties of the
algorithm; communication-wise this is asymptotically optimal.