I&C Journal 1995 Journal Article
Optimal Amortized Distributed Consensus
- A. Barnoy
- X. Deng
- J.A. Garay
- T. Kameda
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.