Optimal amortized distributed consensus

Amotz Barnoy; xiaotie Deng; Juan A. Garay; Tiko Kameda

doi:10.1006/inco.1995.1101

Optimal amortized distributed consensus

Amotz Barnoy
, xiaotie Deng
, Juan A. Garay
, Tiko Kameda

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

11 Citations (Scopus)

Abstract

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³/k), and m* = O(1 + t²/k). When k ≥ t², then r* and m* are O(1) and b*= O(nt), which is optimal. © 1995 Academic Press, Inc.

Original language	English
Pages (from-to)	93-100
Journal	Information and Computation
Volume	120
Issue number	1
DOIs	https://doi.org/10.1006/inco.1995.1101
Publication status	Published - Jul 1995
Externally published	Yes

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Access Output

10.1006/inco.1995.1101

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{e0f7f438d11945029e915e9833d0c2d5,

title = "Optimal amortized distributed consensus",

abstract = "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 + nt3/k), and m* = O(1 + t2/k). When k ≥ t2, then r* and m* are O(1) and b*= O(nt), which is optimal. {\textcopyright} 1995 Academic Press, Inc.",

author = "Amotz Barnoy and xiaotie Deng and Garay, \{Juan A.\} and Tiko Kameda",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "1995",

month = jul,

doi = "10.1006/inco.1995.1101",

language = "English",

volume = "120",

pages = "93--100",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

number = "1",

}

TY - JOUR

T1 - Optimal amortized distributed consensus

AU - Barnoy, Amotz

AU - Deng, xiaotie

AU - Garay, Juan A.

AU - Kameda, Tiko

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 1995/7

Y1 - 1995/7

N2 - 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 + nt3/k), and m* = O(1 + t2/k). When k ≥ t2, then r* and m* are O(1) and b*= O(nt), which is optimal. © 1995 Academic Press, Inc.

AB - 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 + nt3/k), and m* = O(1 + t2/k). When k ≥ t2, then r* and m* are O(1) and b*= O(nt), which is optimal. © 1995 Academic Press, Inc.

UR - http://www.scopus.com/inward/record.url?scp=0043140707&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0043140707&origin=recordpage

U2 - 10.1006/inco.1995.1101

DO - 10.1006/inco.1995.1101

M3 - RGC 21 - Publication in refereed journal

SN - 0890-5401

VL - 120

SP - 93

EP - 100

JO - Information and Computation

JF - Information and Computation

IS - 1

ER -

Optimal amortized distributed consensus

Abstract

Bibliographical note

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this