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

共 11 条

[1] SHIFTING GEARS - CHANGING ALGORITHMS ON THE FLY TO EXPEDITE BYZANTINE AGREEMENT [J].

BARNOY, A ;

DOLEV, D ;

DWORK, C ;

STRONG, HR .

INFORMATION AND COMPUTATION, 1992, 97 (02) :205-233

[2] CONSENSUS ALGORITHMS WITH ONE-BIT MESSAGES [J].

BARNOY, A ;

DOLEV, D .

DISTRIBUTED COMPUTING, 1991, 4 (03) :105-110

[3]

BENOR M, UNPUB INTERACTIVE CO

[4]

BERMAN P, 1992, LECT NOTES COMPUT SC, V647, P221

[5]

BERMAN P, 1991, LECTURE NOTES COMPUT, V579, P129

[6] EARLY STOPPING IN BYZANTINE AGREEMENT [J].

DOLEV, D ;

REISCHUK, R ;

STRONG, HR .

JOURNAL OF THE ACM, 1990, 37 (04) :720-741

[7] BOUNDS ON INFORMATION EXCHANGE FOR BYZANTINE AGREEMENT [J].

DOLEV, D ;

REISCHUK, R .

JOURNAL OF THE ACM, 1985, 32 (01) :191-204

[8]

FELDMAN P, 1988, 20TH P S THEOR COMP, P148

[9] A LOWER BOUND FOR THE TIME TO ASSURE INTERACTIVE CONSISTENCY [J].

FISCHER, MJ ;

LYNCH, NA .

INFORMATION PROCESSING LETTERS, 1982, 14 (04) :183-186

[10]

HADZILACOS V, 1991, MATH SYST THEORY, V26, P41

← 1 2 →