OPTIMAL AMORTIZED DISTRIBUTED CONSENSUS

In this paper we study the behavior of deterministic algorithms when c onsensus is needed repeatedly, say k times. We show that it is possibl e to achieve consensus with the optimal number of processors (n > 3t), and when k is large enough, with optimal amortized cost in all other measures: the number of communication rounds r, the maximal message s ize m, and the total bit complexity b*. More specifically, we achieve the following amortized bounds for k consensus instances: r = O(1 t/k), b = O(nt + nt(3)/k), and m* = O(1 + t(2)/k). When k greater tha n or equal to t(2), then r and m* are O(1) and b*=O(nt), which is opt imal. (C) 1995 Academic Press, Inc.