[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/258533.258649acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article
Free access

Lower bounds for distributed coin-flipping and randomized consensus

Published: 04 May 1997 Publication History
First page of PDF

References

[1]
ttajeev Alur, Hagit Attiya, and Gadi Tanbenfeld. Time-adaptive algorithms for synchronization. In Proceedings of the Twenty. Sixth Annual A CM Symposium on Theory of Computing, pages 800-809, Montreal, Quebec, Canada, may 1994.
[2]
Yonatan Aumann and Michael Bender. Efiicient asynchronous consensus with a valueoblivious adversary scheduler. In Proceedings of the ~3rd International Conference on Automata, Languages, and Program. ruing, July 1996.
[3]
K. Abrahamson. On achieving consensus using a shared memory, in Proceedings of the Seventh A CM SIGACT-SIGOPS Slimposium on Principles of Distributed Computing, August 1988.
[4]
Hagit Attiya, Danny Dolev, and Nit Shavit. Bounded polynomial randomized conseusus. In Proceedings of the Eighth A CM Sllmposium on Principles of Distributed Computing, pages 281-294, August 1989.
[5]
James Aspnes and Maurice Herlihy. Fast randomized consensus using shared mereory. Journal of Algorithms, 11(3):441--461, September 1990.
[6]
Noga Alon and Moni Naor. Coin-flipping games immune against linear-Led coalitions. In Proceedings o! the 31st Annual Symposium on Foundations of Computer Science, pages 46-54. IEEE, 1990.
[7]
James Aspnes. Time- and space-efficient randomized consensus. Journal of Algorithms, 14(3):414--431, May 1993.
[8]
James Aspnes and Orli Waarts. Randomized consensus in O(n logs n) operations per processor. SIAM Journal on Computing, 25(5):1024-1044, October 1996.
[9]
Michael Ben-Or and Nathan Linial. Collective coin flipping, robust voting schemes and minimization of banzhaf values. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science, pages 408-416. IEEE, 1985.
[10]
M. Ben-Or, N. Linial, and M. Saks. Collectire coin flipping and other models of iraperfect randomness. In Combinatorics, volume 52 of Colloquia Mathematic Societatis Jdnos Bolliai, pages 75-112, Eger (Hunguy), 1987.
[11]
Gabi Bracha and Ophir Rachman. Approximated counters and randomized consensus. Technical Report 662, Technion, 1990.
[12]
Gabi Bracha and Ophir Rachman. Randomized consensus in expected O(n21og n) operations. In Proceedings of the Fifth Workshop on Distributed Algorithms, 1991.
[13]
Benny Chor, Joel Friedman, Oded Goldreich, Johan H/mtad, Steven Rudich, and Roman Smolensky. The bit extraction problem or t-resilient functions. In Proceedings o/the,~th Annual Symposium on Foundations of Computer Science, pages 396-407. IEEE, 1985.
[14]
Tushar Deepak Chandra. Polylog randomized wait-free consensus. In Proceedings of the Fifteenth Annual A CM Symposium on Principles of Distributed Computing, pages 166-175, May 1996.
[15]
Richard Cleve and Russell Impagliazzo. Martingales with Boolean final value must make jumps of O(1/n1/2) with constant probability. Unpublished manuscript, 1993.
[16]
B. Chor, A. Israeli, and M. Li. On processor coordination using asynchronous hardware. In Proceedings of the Sixth A CM Symposium on Principles of Distributed Computing, pages 86-97, 1987.
[17]
Jason Cooper and Nathan Linial. Fast perfect-information leader-election protocol with linear immunity. In Proceedings of the Twenty. Fifth Annual A CM Symposium on the Theory o! Computing, pages 662-671. ACM, 1993.
[18]
D. Dolev, C. Dwork, and L. Stockmeyer. On the minimal synchronism needed for distributed consensus. Journal of the A CM, 34(1):77-97, January 1987.
[19]
Cynthia Dwork, Maurice Herlihy, Serge Plotkin, and Orli Waarts. Time-lapse snapshots. In Proceedings of Israel Symposium on the Theory o.t Computing and Systems, 1992.
[20]
Faith Fich, Manrice Herlihy, and Nir Shavit. On the complexity of randomized synchronization. In Proceedings of the l~th Annual ACM Symposium on Principles of Distributed Computing, August 1993.
[21]
M. Fischer, N.A. Lynch, and M.S. Paterson. Im~bility of distributed commit with one faulty process. Journal of the A CM, 32(2), April 1985.
[22]
Joel Friedman. On the bit extraction problem. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 314-319. IEEE, 1992.
[23]
L.H. Harper. Optimal numberings and isoperimetric problems on graphs. Journal o/Combinatorial Theory, 1:385-394, 1966.
[24]
Manrice Herlihy. Wait-free synchronization. A CM Transactions on Programming {,an. guages and Systems, 13(1):124-149, January 1991.
[25]
Michael C. Loui and Hosame H. Abu- Amara. Memory requirements for agreement among unreliable asynchronous processes. In Franco P. Preparata, editor, Advances in Computing Research, volume 4. JAI Press, 1987.
[26]
D. Lichtenstein, N. Linial, and M. Saks. Some extremaJ problems arising from discrete control processes. 6'ombinatorica, 9, 1989.
[27]
Michael Saks. A robust non-cryptographic protocol for collective coin flipping. SIAM Journal on Discrete Mathematics, 2(2):240-- 244, 1989.
[28]
Michael Salts, Nir Shavit, and Heather WoU. Optimal time randomized consensus -- making resilient algorithms fast in practice. In Proceedings of the Second Annual A CM-SIAM Symposium on Discrete A!gorithms, pages 351-362, 1991.
[29]
Umesh Vazirani. Towards a strong communication complexity theory, or generating quasi-random sequences from two communicating slightly-random sources. In Pro. ceedings of the Twenty-Ninth Annual A CM Symposium on the Theory of Computing, pages 366-378. ACM, 1985.

Cited By

View all
  • (2021)Optimally-secure Coin-tossing against a Byzantine Adversary2021 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT45174.2021.9518276(2858-2863)Online publication date: 12-Jul-2021
  • (2020)Computational Hardness of Collective Coin-Tossing ProtocolsEntropy10.3390/e2301004423:1(44)Online publication date: 30-Dec-2020
  • (2017)Probabilistic Byzantine Tolerance Scheduling in Hybrid Cloud EnvironmentsProceedings of the 18th International Conference on Distributed Computing and Networking10.1145/3007748.3007770(1-10)Online publication date: 5-Jan-2017
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing
May 1997
752 pages
ISBN:0897918886
DOI:10.1145/258533
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 May 1997

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

STOC97
Sponsor:

Acceptance Rates

STOC '97 Paper Acceptance Rate 75 of 211 submissions, 36%;
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25
57th Annual ACM Symposium on Theory of Computing (STOC 2025)
June 23 - 27, 2025
Prague , Czech Republic

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)57
  • Downloads (Last 6 weeks)10
Reflects downloads up to 31 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2021)Optimally-secure Coin-tossing against a Byzantine Adversary2021 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT45174.2021.9518276(2858-2863)Online publication date: 12-Jul-2021
  • (2020)Computational Hardness of Collective Coin-Tossing ProtocolsEntropy10.3390/e2301004423:1(44)Online publication date: 30-Dec-2020
  • (2017)Probabilistic Byzantine Tolerance Scheduling in Hybrid Cloud EnvironmentsProceedings of the 18th International Conference on Distributed Computing and Networking10.1145/3007748.3007770(1-10)Online publication date: 5-Jan-2017
  • (2016)Distributed Algorithmic Foundations of Dynamic NetworksACM SIGACT News10.1145/2902945.290295947:1(69-98)Online publication date: 10-Mar-2016
  • (2015)Probabilistic Byzantine Tolerance for Cloud ComputingProceedings of the 2015 IEEE 34th Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS.2015.22(1-10)Online publication date: 28-Sep-2015
  • (2013)Fast byzantine agreement in dynamic networksProceedings of the 2013 ACM symposium on Principles of distributed computing10.1145/2484239.2484275(74-83)Online publication date: 22-Jul-2013
  • (1999)Cooperative sharing and asynchronous consensus using single-reader single-writer registersProceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms10.5555/314500.314532(61-70)Online publication date: 1-Jan-1999
  • (1998)A time complexity lower bound for randomized implementations of some shared objectsProceedings of the seventeenth annual ACM symposium on Principles of distributed computing10.1145/277697.277735(201-210)Online publication date: 1-Jun-1998
  • (1998)A tight lower bound for randomized synchronous consensusProceedings of the seventeenth annual ACM symposium on Principles of distributed computing10.1145/277697.277733(193-199)Online publication date: 1-Jun-1998
  • (1997)Efficient asynchronous consensus with the weak adversary schedulerProceedings of the sixteenth annual ACM symposium on Principles of distributed computing10.1145/259380.259441(209-218)Online publication date: 1-Aug-1997

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media