Article

Randomized Consensus in Expected O(n²log n) Operations

Authors:

Gabriel Bracha,

Ophir RachmanAuthors Info & Claims

WDAG '91: Proceedings of the 5th International Workshop on Distributed Algorithms

Pages 143 - 150

Published: 07 October 1991 Publication History

Abstract

No abstract available.

Cited By

View all

Alistarh DAspnes JKing VSaia J(2018)Communication-efficient randomized consensusDistributed Computing10.1007/s00446-017-0315-131:6(489-501)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1007/s00446-017-0315-1
Gogolev AMarchenko NMarcenaro LBettstetter C(2015)Distributed Binary Consensus in Networks with DisturbancesACM Transactions on Autonomous and Adaptive Systems10.1145/274634710:3(1-17)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1145/2746347
Aspnes J(2011)Randomized consensus in expected O(n2) total work using single-writer registersProceedings of the 25th international conference on Distributed computing10.5555/2075029.2075077(363-373)Online publication date: 20-Sep-2011
https://dl.acm.org/doi/10.5555/2075029.2075077
Show More Cited By

Recommendations

Faster randomized consensus with an oblivious adversary

Two new algorithms are given for randomized consensus in a shared-memory model with an oblivious adversary. Each is based on a new construction of a conciliator, an object that guarantees termination and validity, but that only guarantees agreement with ...
Faster randomized consensus with an oblivious adversary
PODC '12: Proceedings of the 2012 ACM symposium on Principles of distributed computing

Two new algorithms are given for randomized consensus in a shared-memory model with an oblivious adversary. Each is based on a new construction of a conciliator, an object that guarantees termination and validity, but that only guarantees agreement with ...
Randomized consensus in expected O(n log/sup 2/ n) operations per processor
SFCS '92: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science

The paper presents a new randomized algorithm for achieving consensus among asynchronous processors that communicate by reading and writing shared registers. The fastest previously known algorithm requires a processor to perform an expected O(n/sup 2/ ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

WDAG '91: Proceedings of the 5th International Workshop on Distributed Algorithms

October 1991

318 pages

ISBN:3540552367

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 07 October 1991

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Alistarh DAspnes JKing VSaia J(2018)Communication-efficient randomized consensusDistributed Computing10.1007/s00446-017-0315-131:6(489-501)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1007/s00446-017-0315-1
Gogolev AMarchenko NMarcenaro LBettstetter C(2015)Distributed Binary Consensus in Networks with DisturbancesACM Transactions on Autonomous and Adaptive Systems10.1145/274634710:3(1-17)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1145/2746347
Aspnes J(2011)Randomized consensus in expected O(n2) total work using single-writer registersProceedings of the 25th international conference on Distributed computing10.5555/2075029.2075077(363-373)Online publication date: 20-Sep-2011
https://dl.acm.org/doi/10.5555/2075029.2075077
Censor Hillel Kauf der Heide FPhillips C(2010)Multi-sided shared coins and randomized set-agreementProceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures10.1145/1810479.1810490(60-68)Online publication date: 13-Jun-2010
https://dl.acm.org/doi/10.1145/1810479.1810490
Aspnes JCensor K(2010)Approximate shared-memory counting despite a strong adversaryACM Transactions on Algorithms10.1145/1721837.17218416:2(1-23)Online publication date: 6-Apr-2010
https://dl.acm.org/doi/10.1145/1721837.1721841
Aspnes JAttiya HCensor K(2010)Combining shared-coin algorithmsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2009.08.00570:3(317-322)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1016/j.jpdc.2009.08.005
Aspnes JCensor KMathieu C(2009)Approximate shared-memory counting despite a strong adversaryProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms10.5555/1496770.1496819(441-450)Online publication date: 4-Jan-2009
https://dl.acm.org/doi/10.5555/1496770.1496819
Chlebus BKowalski DMeyer auf der Heide FBender M(2009)Locally scalable randomized consensus for synchronous crash failuresProceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures10.1145/1583991.1584063(290-299)Online publication date: 11-Aug-2009
https://dl.acm.org/doi/10.1145/1583991.1584063
Attiya HCensor K(2008)Tight bounds for asynchronous randomized consensusJournal of the ACM10.1145/1411509.141151055:5(1-26)Online publication date: 5-Nov-2008
https://dl.acm.org/doi/10.1145/1411509.1411510
Aspnes JAttiya HCensor KBazzi RPatt-Shamir B(2008)Randomized consensus in expected O(n log n) individual workProceedings of the twenty-seventh ACM symposium on Principles of distributed computing10.1145/1400751.1400794(325-334)Online publication date: 18-Aug-2008
https://dl.acm.org/doi/10.1145/1400751.1400794
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Recommendations

Faster randomized consensus with an oblivious adversary

Faster randomized consensus with an oblivious adversary

Randomized consensus in expected O(n log/sup 2/ n) operations per processor

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations