Early-Stabilizing Counting

Abstract

Synchronous Counting is the task of reaching agreement on a common round counter in a synchronous system of n nodes with up to t Byzantine faults in a self-stabilizing manner. That is, after transient faults may have arbitrarily corrupted the system state and ceased, the at least n - t non-faulty nodes need to (re-)establish that (i) their local outputs are identical and (ii) increase by 1 modulo C in each round. An overhead-free reduction from consensus shows that all known lower bounds and impossibilities for consensus carry over to the counting problem. In the other direction, prior work has established that a consensus algorithm A can be turned into a counting algorithm at small overhead relative to the running time and bit complexity of A, without losing resilience.Taking inspiration from early-stopping consensus protocols, in this work we introduce the concept of early stabilization. That is, if there are 0 ≤ f ≤ t (persistent) faults in an execution, the algorithm should stabilize in a number of rounds that depends on f only. Likewise, we seek to achieve an amortized bit complexity that is adaptive in the number of actual faults f. By developing a number of modular building blocks suitable to these goals, we develop a C-counting algorithm that stabilizes within asymptotically optimal O(f + 1) rounds, has message size O(log2 n + log C), and has amortized bit complexity O(n(f log C + log2 n)).