[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/1810479.1810494acmconferencesArticle/Chapter ViewAbstractPublication PagesspaaConference Proceedingsconference-collections
short-paper

Brief announcement: byzantine agreement with homonyms

Published: 13 June 2010 Publication History

Abstract

In this work, we address Byzantine agreement in a message passing system with homonyms, i.e. a system with a number l of authenticated identities that is independent of the total number of processes n, in the presence of t < n Byzantine processes.
We prove the following results: (i) agreement is possible if (and only if) l > 3t in a synchronous model; (ii) agreement is impossible, independently of the number of failures, in an eventually synchronous model; (iii) eventual agreement is possible, if (and only if) l > 3t, in an asynchronous model.

References

[1]
Dana Angluin, Michael J. Fischer, and Hong Jiang. Stabilizing consensus in mobile networks. In DCOSS, volume 4026 of LNCS, pages 37--50, 2006.
[2]
Hagit Attiya, Alla Gorbach, and Shlomo Moran. Computing in totally anonymous asynchronous shared memory systems. Inf. Comput., 173(2):162--183, 2002.
[3]
Hagit Attiya and Jennifer Welch. Distributed Computing: fundamentals, simulations and advanced topics, 2nd edition. Wiley, 2004.
[4]
Harry Buhrman, Alessandro Panconesi, Riccardo Silvestri, and Paul M. B. Vitányi. On the importance of having an identity or, is consensus really universal? Distributed Computing, 18(3):167--176, 2006.
[5]
Cynthia Dwork, Nancy A. Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):288--323, April 1988.
[6]
Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374--382, April 1985.
[7]
Rachid Guerraoui and Eric Ruppert. Anonymous and fault-tolerant shared-memory computing. Distributed Computing, 20(3):165--177, 2007.
[8]
Rachid Guerraoui and Eric Ruppert. Names trump malice: Tiny mobile agents can tolerate byzantine failures. In ICALP, volume 5556 of LNCS, pages 484--495. Springer, 2009.
[9]
Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996.
[10]
Achour Mostéfaoui, Michel Raynal, and Frederic Tronel. From binary consensus to multivalued consensus in asynchronous message-passing systems. Inf. Process. Lett., 73(5-6):207--212, 2000.
[11]
Michael Okun and Amnon Barak. Efficient algorithms for anonymous byzantine agreement. Theory Comput. Syst., 42(2):222--238, 2008.
[12]
Antony I. T. Rowstron and Peter Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In Middleware, volume 2218 of LNCS, pages 329--350, 2001.
[13]
Eric Ruppert. The anonymous consensus hierarchy and naming problems. In OPODIS, volume 4878 of LNCS, pages 386--400. Springer, 2007.
[14]
Ion Stoica, Robert Morris, David R. Karger, M. Frans Kaashoek, and Hari Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In ACM SIGCOMM, pages 149--160, 2001.
[15]
Xiaoyun Wang and Hongbo Yu. How to break md5 and other hash functions. In EUROCRYPT, volume 3494 of LNCS, pages 19--35, 2005.

Cited By

View all
  • (2011)Byzantine agreement with homonymsProceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1993806.1993810(21-30)Online publication date: 6-Jun-2011

Index Terms

  1. Brief announcement: byzantine agreement with homonyms

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SPAA '10: Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures
    June 2010
    378 pages
    ISBN:9781450300797
    DOI:10.1145/1810479

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 13 June 2010

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. authentication
    2. byzantine agreement
    3. consensus
    4. message-passing

    Qualifiers

    • Short-paper

    Conference

    SPAA 10

    Acceptance Rates

    Overall Acceptance Rate 447 of 1,461 submissions, 31%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 11 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2011)Byzantine agreement with homonymsProceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1993806.1993810(21-30)Online publication date: 6-Jun-2011

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media