On Dynamic Distributed Computing

Abstract. The history of distributed computing is strongly tied to the assumption of a static network composed predominantly of honest nodes. Yet, many modern distributed systems not only are not static but exhibit a high level of churn. This paper demonstrates how to achieve distributed computing in a highly dynamic environment despite the presence of a static Byzantine adversary controlling a large fraction of the nodes. Somewhat surprisingly, we prove that it is possible to maintain clusters of nodes with a majority of honest ones in each in an efficient manner, within a system whose size can change polynomially compare to the initial size of the network. As a corollary of our construction, we solve an open problem in distributed computing. Our construction also provides a basic abstraction enabling for the first time several types of distributed coordination in a highly dynamic setting, such as peer sampling, broadcast, Byzantine agreement and aggregation. More specifically, we assume a static Byzantine adversary controlling a fraction τ ≤ 1 2l2 − of the nodes (for some fixed constants l> 2 and > 0, independent of N, the maximal size of the system). To the best of our knowledge, we are the first to show how to maintain at low cost, in terms of computation and communication, an overlay partitioning the nodes into clusters of size O(log2N), each containing a majority of honest nodes with high probability. Another algorithm displaying a low complexity, which we call NOW (for Neighbors On Watch), preserves this property in the presence of high churn (up to a polynomial increase and decrease of the number of nodes). The algorithm NOW itself relies on another novel algorithm called OVER (for Over: Valued Erdös Rényi graph), which maintains an overlay with high expansion coefficient and low degree. In a nutshell, NOW can achieve dynamic clustering with a low complexity, namely with a communication cost induced by each node arrival or departure that is polylogarithmic with respect to the maximal size of the system. a