Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler

Yonatan Aumann; Michael A. Bender

doi:10.1007/s00446-004-0113-4

Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler

Yonatan Aumann
, Michael A. Bender

Computer Science

Stony Brook University

Bar-Ilan University

Research output: Contribution to journal › Article › peer-review

11 Scopus citations

Abstract

We consider asynchronous consensus in the shared-memory setting. We present the first efficient low-contention consensus algorithm for the weak-adversary-scheduler model. The algorithm achieves consensus in O(nlog ²n) total work and O(log n) (hot-spot) contention, both expected and with high probability. The algorithm assumes the value-oblivious scheduler, which is defined in the paper. Previous efficient consensus algorithms for weak adversaries suffer from Ω(n) memory contention.

Original language	English
Pages (from-to)	191-207
Number of pages	17
Journal	Distributed Computing
Volume	17
Issue number	3
DOIs	https://doi.org/10.1007/s00446-004-0113-4
State	Published - Mar 2005

Access to Document

10.1007/s00446-004-0113-4

Cite this

@article{97833a4c5725405196787445ee4d913b,

title = "Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler",

abstract = "We consider asynchronous consensus in the shared-memory setting. We present the first efficient low-contention consensus algorithm for the weak-adversary-scheduler model. The algorithm achieves consensus in O(nlog 2n) total work and O(log n) (hot-spot) contention, both expected and with high probability. The algorithm assumes the value-oblivious scheduler, which is defined in the paper. Previous efficient consensus algorithms for weak adversaries suffer from Ω(n) memory contention.",

author = "Yonatan Aumann and Bender, \{Michael A.\}",

year = "2005",

month = mar,

doi = "10.1007/s00446-004-0113-4",

language = "English",

volume = "17",

pages = "191--207",

journal = "Distributed Computing",

issn = "0178-2770",

publisher = "Springer Verlag",

number = "3",

}

TY - JOUR

T1 - Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler

AU - Aumann, Yonatan

AU - Bender, Michael A.

PY - 2005/3

Y1 - 2005/3

N2 - We consider asynchronous consensus in the shared-memory setting. We present the first efficient low-contention consensus algorithm for the weak-adversary-scheduler model. The algorithm achieves consensus in O(nlog 2n) total work and O(log n) (hot-spot) contention, both expected and with high probability. The algorithm assumes the value-oblivious scheduler, which is defined in the paper. Previous efficient consensus algorithms for weak adversaries suffer from Ω(n) memory contention.

AB - We consider asynchronous consensus in the shared-memory setting. We present the first efficient low-contention consensus algorithm for the weak-adversary-scheduler model. The algorithm achieves consensus in O(nlog 2n) total work and O(log n) (hot-spot) contention, both expected and with high probability. The algorithm assumes the value-oblivious scheduler, which is defined in the paper. Previous efficient consensus algorithms for weak adversaries suffer from Ω(n) memory contention.

UR - https://www.scopus.com/pages/publications/17044438769

U2 - 10.1007/s00446-004-0113-4

DO - 10.1007/s00446-004-0113-4

M3 - Article

SN - 0178-2770

VL - 17

SP - 191

EP - 207

JO - Distributed Computing

JF - Distributed Computing

IS - 3

ER -

Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler

Abstract

Access to Document

Other files and links

Fingerprint

Cite this