Optimal Amortized Distributed Consensus

In this paper we study the behavior of deterministic algorithms when consensus is needed repeatedly, say k times. We show that it is possible 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 size 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 ≥ t 2, then r* and m* are O(1) and b*= O(nt), which is optimal.

Authors

• A. Barnoy
• X. Deng
• J.A. Garay
• T. Kameda

Keywords

No keywords are indexed for this paper.