Julian Loss

Christoph Lenzen, Julian Loss

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 $\mathcal{A}$ can be turned into a counting algorithm at small overhead relative to the running time and bit complexity of $\mathcal{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\le f\le 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(\log^2 n + \log C)$, and has amortized bit complexity $O(n(f\log C +\log^2 n))$.

Erica Blum, Jonathan Katz, Julian Loss

We study the problem of state machine replication (SMR)---the underlying problem addressed by blockchain protocols---in the presence of a malicious adversary who can corrupt some fraction of the parties running the protocol. Existing protocols for this task assume either a synchronous network (where all messages are delivered within some known time $Δ$) or an asynchronous network (where messages can be delayed arbitrarily). Although protocols for the latter case give seemingly stronger guarantees, this is not the case since they (inherently) tolerate a lower fraction of corrupted parties. We design an SMR protocol that is network-agnostic in the following sense: if it is run in a synchronous network, it tolerates $t_s$ corrupted parties; if the network happens to be asynchronous it is resilient to $t_a \leq t_s$ faults. Our protocol achieves optimal tradeoffs between $t_s$ and $t_a$.