OPTIMAL AMORTIZED DISTRIBUTED CONSENSUS

被引：8

作者：

BARNOY, A ^{[1
]}

DENG, X ^{[1
]}

GARAY, JA ^{[1
]}

KAMEDA, T ^{[1
]}

机构：

[1] SIMON FRASER UNIV,SCH COMP SCI,BURNABY,BC V5A 1S6,CANADA

来源：

INFORMATION AND COMPUTATION | 1995年 / 120卷 / 01期

关键词：

D O I：

10.1006/inco.1995.1101

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 greater than or equal to t(2), then r* and m* are O(1) and b*=O(nt), which is optimal. (C) 1995 Academic Press, Inc.

引用

页码：93 / 100

页数：8