Efficient agreement on bounded-degree networks

Piotr Berman; Juan A. Garay

Efficient agreement on bounded-degree networks

Piotr Berman, Juan A. Garay

Research output: Contribution to journal › Conference article › peer-review

Abstract

The distributed consensus problem requires n correct processors to reach consensus in the presence of the arbitrary behavior of t faulty processors. The authors show how to achieve consensus on a bounded-degree network in the presence of O(n/log n) faulty processors in time O(n). Improvement on previous results is achieved, which implies that consensus can be reached in this setting in time Ω(n³).

Original language	English (US)
Pages (from-to)	188-191
Number of pages	4
Journal	Proceedings of the International Conference on Parallel Processing
Volume	1
State	Published - 1989
Event	Proceedings of the 1989 International Conference on Parallel Processing - University Park, PA, USA Duration: Aug 8 1989 → Aug 12 1989

All Science Journal Classification (ASJC) codes

Hardware and Architecture

Cite this

@article{ba3154548c5b4e11803e6b1ce7a6171a,

title = "Efficient agreement on bounded-degree networks",

abstract = "The distributed consensus problem requires n correct processors to reach consensus in the presence of the arbitrary behavior of t faulty processors. The authors show how to achieve consensus on a bounded-degree network in the presence of O(n/log n) faulty processors in time O(n). Improvement on previous results is achieved, which implies that consensus can be reached in this setting in time Ω(n3).",

author = "Piotr Berman and Garay, {Juan A.}",

year = "1989",

language = "English (US)",

volume = "1",

pages = "188--191",

journal = "Proceedings of the International Conference on Parallel Processing",

issn = "0190-3918",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "Proceedings of the 1989 International Conference on Parallel Processing ; Conference date: 08-08-1989 Through 12-08-1989",

}

TY - JOUR

T1 - Efficient agreement on bounded-degree networks

AU - Berman, Piotr

AU - Garay, Juan A.

PY - 1989

Y1 - 1989

N2 - The distributed consensus problem requires n correct processors to reach consensus in the presence of the arbitrary behavior of t faulty processors. The authors show how to achieve consensus on a bounded-degree network in the presence of O(n/log n) faulty processors in time O(n). Improvement on previous results is achieved, which implies that consensus can be reached in this setting in time Ω(n3).

AB - The distributed consensus problem requires n correct processors to reach consensus in the presence of the arbitrary behavior of t faulty processors. The authors show how to achieve consensus on a bounded-degree network in the presence of O(n/log n) faulty processors in time O(n). Improvement on previous results is achieved, which implies that consensus can be reached in this setting in time Ω(n3).

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

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

M3 - Conference article

AN - SCOPUS:0024943656

SN - 0190-3918

VL - 1

SP - 188

EP - 191

JO - Proceedings of the International Conference on Parallel Processing

JF - Proceedings of the International Conference on Parallel Processing

T2 - Proceedings of the 1989 International Conference on Parallel Processing

Y2 - 8 August 1989 through 12 August 1989

ER -

Efficient agreement on bounded-degree networks

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this