More Web Proxy on the site http://driver.im/

research-article

Public Access

A Fully-Distributed Scalable Peer-to-Peer Protocol for Byzantine-Resilient Distributed Hash Tables

Authors:

John Augustine,

Soumyottam Chatterjee,

Gopal PanduranganAuthors Info & Claims

SPAA '22: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures

Pages 87 - 98

https://doi.org/10.1145/3490148.3538588

Published: 11 July 2022 Publication History

Abstract

Performing computation in the presence of faulty and malicious nodes is a central problem in distributed computing. Over 35 years ago, Dwork, Peleg, Pippenger, and Upfal [STOC 1986, SICOMP 1988] studied the fundamental Byzantine agreement problem in sparse, bounded degree networks and presented the first protocol that achieved almost-everywhere agreement among good nodes. However, this protocol and several subsequent protocols including that of King, Saia, Sanwalani, and Vee [FOCS 2006] had the drawback that they were not fully-distributed - in those protocols, nodes are required to have initial knowledge of the entire network topology. This drawback makes such protocols not applicable to real-world communication networks such as peer-to-peer (P2P) networks, which are typically sparse and bounded degree and where nodes initially have only local knowledge of themselves and of their neighbors.

References

[1]

[n.d.]. Freenet. https://freenetproject.org/. Accessed: 2018-07--16.

[2]

[n.d.]. Website of BitTorrent. https://www.bittorrent.com/. Accessed: 2018-07--15.

[3]

Ittai Abraham, Dahlia Malkhi, and Oren Dobzinski. 2004. LAND: Stretch (1 + ) Locality-Aware Networks for DHTs. In Proceedings of the Fifteenth Annual ACMSIAM Symposium on Discrete Algorithms (New Orleans, Louisiana) (SODA '04). Society for Industrial and Applied Mathematics, USA, 550--559.

[4]

John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, and Jared Saia. 2020. Scalable and Secure Computation Among Strangers: Message- Competitive Byzantine Protocols. In 34th International Symposium on Distributed Computing (DISC 2020) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 179), Hagit Attiya (Ed.). Schloss Dagstuhl--Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 31:1--31:19. https://doi.org/10.4230/LIPIcs.DISC.2020.31

[5]

John Augustine, Anisur Rahaman Molla, Ehab Morsy, Gopal Pandurangan, Peter Robinson, and Eli Upfal. 2013. Storage and Search in Dynamic Peer-to-peer Networks. In Proceedings of the Twenty-fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures (Montréal, Québec, Canada) (SPAA '13). ACM, New York, NY, USA, 53--62. https://doi.org/10.1145/2486159.2486170

Digital Library

[6]

John Augustine, Gopal Pandurangan, and Peter Robinson. 2013. Fast Byzantine Agreement in Dynamic Networks. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (Montréal, Québec, Canada) (PODC '13). ACM, New York, NY, USA, 74--83. https://doi.org/10.1145/2484239. 2484275

Digital Library

[7]

John Augustine, Gopal Pandurangan, and Peter Robinson. 2015. Fast Byzantine Leader Election in Dynamic Networks. In Proceedings of the 29th International Symposium on Distributed Computing - Volume 9363 (Tokyo, Japan) (DISC 2015). Springer-Verlag New York, Inc., New York, NY, USA, 276--291. https://doi.org/ 10.1007/978--3--662--48653--5_19

[8]

John Augustine, Gopal Pandurangan, Peter Robinson, Scott Roche, and Eli Upfal. 2015. Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to- Peer Networks. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS '15). 350--369. https://doi.org/10.1109/FOCS.2015.29

Digital Library

[9]

John Augustine, Gopal Pandurangan, Peter Robinson, and Eli Upfal. 2012. Towards Robust and Efficient Computation in Dynamic Peer-to-peer Networks. In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms (Kyoto, Japan) (SODA '12). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 551--569. http://dl.acm.org/citation.cfm?id= 2095116.2095163

Digital Library

[10]

John Augustine and Sumathi Sivasubramaniam. 2018. Spartan: A Framework For Sparse Robust Addressable Networks. In 2018 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018, Vancouver, BC, Canada, May 21--25, 2018. 1060--1069. https://doi.org/10.1109/IPDPS.2018.00115

[11]

Baruch Awerbuch and Christian Scheideler. 2004. Group Spreading: A Protocol for Provably Secure Distributed Name Service. In Automata, Languages and Programming (ICALP '04), Josep Díaz, Juhani Karhumäki, Arto Lepistö, and Donald Sannella (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 183--195.

[12]

Baruch Awerbuch and Christian Scheideler. 2004. The Hyperring: A Lowcongestion Deterministic Data Structure for Distributed Environments. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, Louisiana) (SODA '04). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 318--327. http://dl.acm.org/citation.cfm?id= 982792.982836

[13]

Baruch Awerbuch and Christian Scheideler. 2007. Towards Scalable and Robust Overlay Networks. In 6th International workshop on Peer-To-Peer Systems, IPTPS 2007, Bellevue, WA, USA, February 26--27, 2007, John R. Douceur and Roger Wattenhofer (Eds.). http://www.iptps.org/papers-2007/AwerbuchScheideler.pdf

[14]

Baruch Awerbuch and Christian Scheideler. 2009. Robust random number generation for peer-to-peer systems. Theoretical Computer Science 410, 6 (2009), 453--466. https://doi.org/10.1016/j.tcs.2008.10.003

Digital Library

[15]

Baruch Awerbuch and Christian Scheideler. 2009. Towards a Scalable and Robust DHT. Theory of Computing Systems 45, 2 (01 August 2009), 234--260. https: //doi.org/10.1007/s00224-008--9099--9

[16]

Michael Ben-Or. 1983. Another Advantage of Free Choice (Extended Abstract): Completely Asynchronous Agreement Protocols. In Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing (Montreal, Quebec, Canada) (PODC '83). Association for Computing Machinery, New York, NY, USA, 27--30. https://doi.org/10.1145/800221.806707

Digital Library

[17]

Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. 1988. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation. In SPAA '22, July 11--14, 2022, Philadelphia, PA, USA Augustine, Chatterjee, and Pandurangan Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (Chicago, Illinois, USA) (STOC '88).

[18]

Michael Ben-Or, Elan Pavlov, and Vinod Vaikuntanathan. 2006. Byzantine Agreement in the Full-information Model in (log) Rounds. In Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing (Seattle, WA, USA) (STOC '06). ACM, New York, NY, USA, 179--186. https: //doi.org/10.1145/1132516.1132543

Digital Library

[19]

Piotr Berman and Juan A. Garay. 1993. Cloture Votes: ( 4 )-Resilient Distributed Consensus in ( + 1) Rounds. Mathematical Systems Theory 26, 1 (1993), 3--19. https://doi.org/10.1007/BF01187072

[20]

Piotr Berman and Juan A. Garay. 1993. Fast Consensus in Networks of Bounded Degree. Distributed Computing 7, 2 (December 1993), 67--73. https://doi.org/10. 1007/BF02280836

Digital Library

[21]

David Chaum, Claude Crépeau, and Ivan Damgård. 1988. Multiparty Unconditionally Secure Protocols (Extended Abstract). In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC). ACM, 11--19.

Digital Library

[22]

Colin Cooper, Martin Dyer, and Catherine Greenhill. 2007. Sampling Regular Graphs and a Peer-to-Peer Network. Combinatorics, Probability, and Computing 16, 4 (July 2007), 557--593. https://doi.org/10.1017/S0963548306007978

Digital Library

[23]

Danny Dolev, Michael J. Fischer, Rob Fowler, Nancy A. Lynch, and H. Raymond Strong. 1982. An efficient algorithm for byzantine agreement without authentication. Information and Control 52, 3 (1982), 257--274. https://doi.org/10.1016/S0019- 9958(82)90776--8

[24]

Cynthia Dwork, David Peleg, Nicholas Pippenger, and Eli Upfal. 1988. Fault Tolerance in Networks of Bounded Degree. SIAM J. Comput. 17, 5 (1988), 975--988. https://doi.org/10.1137/0217061 arXiv:https://doi.org/10.1137/0217061 Conference version in STOC 1986.

Digital Library

[25]

Pesech Feldman and Silvio Micali. 1997. An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement. SIAM J. Comput. 26, 4 (August 1997), 873--933. https://doi.org/10.1137/S0097539790187084

Digital Library

[26]

Christos Gkantsidis, Milena Mihail, and Amin Saberi. 2006. Random walks in peer-to-peer networks: Algorithms and evaluation. Performance Evaluation 63, 3 (2006), 241--263. https://doi.org/10.1016/j.peva.2005.01.002 P2P Computing Systems.

Digital Library

[27]

Thorsten Götte, Kristian Hinnenthal, Christian Scheideler, and JulianWerthmann. 2021. Time-Optimal Construction of Overlay Networks. In PODC '21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26--30, 2021, Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen (Eds.). ACM, 457--468.

[28]

Rachid Guerraoui, Florian Huc, and Anne-Marie Kermarrec. 2013. Highly Dynamic Distributed Computing with Byzantine Failures. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (Montréal, Québec, Canada) (PODC '13). ACM, New York, NY, USA, 176--183. https: //doi.org/10.1145/2484239.2484263

Digital Library

[29]

Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, and Hanjo Täubig. 2014. SKIP+: A Self-Stabilizing Skip Graph. Journal of the ACM 61, 6, Article 36 (December 2014), 26 pages. https://doi.org/10.1145/2629695

Digital Library

[30]

Tim Jacobs and Gopal Pandurangan. 2013. Stochastic analysis of a churn-tolerant structured peer-to-peer scheme. Peer-to-Peer Networking and Applications 6, 1 (01 March 2013), 1--14. https://doi.org/10.1007/s12083-012-0124-z

[31]

Bruce M. Kapron, David Kempe, Valerie King, Jared Saia, and Vishal Sanwalani. 2010. Fast Asynchronous Byzantine Agreement and Leader Election with Full Information. ACM Transactions on Algorithms 6, 4, Article 68 (September 2010), 28 pages. https://doi.org/10.1145/1824777.1824788

Digital Library

[32]

Valerie King and Jared Saia. 2011. Breaking the (2) Bit Barrier: Scalable Byzantine Agreement with an Adaptive Adversary. Journal of the ACM 58, 4, Article 18 (July 2011), 24 pages. https://doi.org/10.1145/1989727.1989732

Digital Library

[33]

Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. 2006. Scalable Leader Election. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (Miami, Florida) (SODA '06). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 990--999. http://dl.acm.org/citation.cfm? id=1109557.1109667

Digital Library

[34]

Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. 2006. Towards Secure and Scalable Computation in Peer-to-Peer Networks. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). 87--98. https://doi. org/10.1109/FOCS.2006.77

[35]

Ching Law and Kai-Yeung Siu. 2003. Distributed construction of random expander networks. In IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No.03CH37428), Vol. 3. 2133--2143 vol.3. https://doi.org/10.1109/INFCOM.2003.1209234

[36]

Peter Mahlmann and Christian Schindelhauer. 2006. Distributed Random Digraph Transformations for Peer-to-Peer Networks. In Proceedings of the Eighteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures (Cambridge, Massachusetts, USA) (SPAA '06). Association for Computing Machinery, New York, NY, USA, 308--317. https://doi.org/10.1145/1148109.1148162

Digital Library

[37]

Dahlia Malkhi, Moni Naor, and David Ratajczak. 2002. Viceroy: A Scalable and Dynamic Emulation of the Butterfly. In Proceedings of the Twenty-first Annual Symposium on Principles of Distributed Computing (Monterey, California) (PODC '02). ACM, New York, NY, USA, 183--192. https://doi.org/10.1145/571825.571857

Digital Library

[38]

Yifan Mao, Soubhik Deb, Shaileshh Bojja Venkatakrishnan, Sreeram Kannan, and Kannan Srinivasan. 2020. Perigee: Efficient Peer-to-Peer Network Design for Blockchains. In Proceedings of the 39th Symposium on Principles of Distributed Computing (Virtual Event, Italy) (PODC '20). Association for Computing Machinery, New York, NY, USA, 428--437. https://doi.org/10.1145/3382734.3405704

Digital Library

[39]

Petar Maymounkov and David Mazières. 2002. Kademlia: A Peer-to-Peer Information System Based on the XOR Metric. In Peer-to-Peer Systems, Peter Druschel, Frans Kaashoek, and Antony Rowstron (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 53--65.

[40]

Silvio Micali and Tal Rabin. 1990. Collective Coin Tossing Without Assumptions nor Broadcasting. In Advances in Cryptology - CRYPTO '90, 10th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11--15, 1990, Proceedings. 253--266.

[41]

Michael Mitzenmacher and Eli Upfal. 2017. Probability and Computing: Randomized Algorithms and Probabilistic Analysis (2nd ed.). Cambridge University Press, Cambridge CB2 8BS, United Kingdom. http://www.cambridge.org/ 9781107154889

Digital Library

[42]

Edgar M. Palmer. 1985. Graphical Evolution: An Introduction to the Theory of Random Graphs. John Wiley & Sons, Inc., USA.

Digital Library

[43]

Gopal Pandurangan, Prabhakar Raghavan, and Eli Upfal. 2003. Building lowdiameter peer-to-peer networks. IEEE Journal on Selected Areas in Communications 21, 6 (August 2003), 995--1002. https://doi.org/10.1109/JSAC.2003.814666 Conference version: IEEE Symposium on the Foundations of Computer Science (FOCS), 2001.

Digital Library

[44]

Gopal Pandurangan, Peter Robinson, and Amitabh Trehan. 2016. DEX: selfhealing expanders. Distributed Computing 29, 3 (01 June 2016), 163--185. https: //doi.org/10.1007/s00446-015-0258--3

[45]

Gopal Pandurangan and Amitabh Trehan. 2014. Xheal: a localized self-healing algorithm using expanders. Distributed Computing 27, 1 (01 February 2014), 39--54. https://doi.org/10.1007/s00446-013-0192--1

[46]

Marshall C. Pease, Robert E. Shostak, and Leslie Lamport:. 1980. Reaching Agreement in the Presence of Faults. Journal of the ACM 27, 2 (April 1980), 228--234. https://doi.org/10.1145/322186.322188

Digital Library

[47]

David Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9780898719772 arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9780898719772

[48]

Michael O. Rabin. 1983. Randomized Byzantine Generals. In Proceedings of the 24th Annual Symposium on Foundations of Computer Science (SFCS '83). IEEE Computer Society, USA, 403--409. https://doi.org/10.1109/SFCS.1983.48

Digital Library

[49]

Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker. 2001. A Scalable Content-addressable Network. ACM SIGCOMM Computer Communication Review 31, 4 (August 2001), 161--172. https://doi.org/10.1145/ 964723.383072

Digital Library

[50]

Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, and Hari Balakrishnan. 2003. Chord: A Scalable Peerto- peer Lookup Protocol for Internet Applications. IEEE/ACM Transactions on Networking (TON) 11, 1 (February 2003), 17--32. https://doi.org/10.1109/TNET. 2002.808407

[51]

Eli Upfal. 1994. Tolerating a Linear Number of Faults in Networks of Bounded Degree. Information and Computation 115, 2 (1994), 312--320. https://doi.org/10. 1006/inco.1994.1099

Digital Library

[52]

Leslie Gabriel Valiant. 1982. A Scheme for Fast Parallel Communication. SIAM J. Comput. 11, 2 (1982), 350--361. https://doi.org/10.1137/0211027 arXiv:https://doi.org/10.1137/0211027

Digital Library

Cited By

Abassi RRiahla MTamine KGoumiri S(2024)Towards a Formal MultipathP2P ProtocolInternational Journal of Business Data Communications and Networking10.4018/IJBDCN.34441619:1(1-13)Online publication date: 21-Jun-2024
https://dl.acm.org/doi/10.4018/IJBDCN.344416
Król MAscigil ORene SSonnino APigaglio MSadre RLange FRivière E(2024)DISC-NG: Robust Service Discovery in the Ethereum Global Network2024 IEEE 9th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP60621.2024.00019(193-215)Online publication date: 8-Jul-2024
https://doi.org/10.1109/EuroSP60621.2024.00019
Tseng LAmbarapu LAloqaily M(2024)NC-DHT: a Robust and Anonymous DHT for Blockchain Systems2024 6th International Conference on Blockchain Computing and Applications (BCCA)10.1109/BCCA62388.2024.10844445(394-399)Online publication date: 26-Nov-2024
https://doi.org/10.1109/BCCA62388.2024.10844445
Show More Cited By

Index Terms

A Fully-Distributed Scalable Peer-to-Peer Protocol for Byzantine-Resilient Distributed Hash Tables
1. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms

Recommendations

Cost-effective broadcast for fully decentralized peer-to-peer networks

Fully unstructured and decentralized peer-to-peer networks such as Gnutella are appealing for a variety of applications, among which file-sharing is the most prominent one. The decentralized nature of these systems provides a high degree of robustness ...
Building resilient low-diameter peer-to-peer topologies

As more applications rely on underlying peer-to-peer topologies, the need for efficient and resilient infrastructure has become more pressing. A number of important classes of topologies have emerged over the last several years, all with various ...
A connection management protocol for promoting cooperation in Peer-to-Peer networks

The existence of a high degree of free riding in Peer-to-Peer (P2P) networks is an important threat that should be addressed while designing P2P protocols. In this paper we propose a connection-based solution that will help to reduce the free riding ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '22: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures

July 2022

464 pages

ISBN:9781450391467

DOI:10.1145/3490148

General Chair:
Kunal Agrawal
Washington University in St. Louis, USA
,
Program Chair:
I-Ting Angelina Lee
Washington University in St. Louis, USA

Copyright © 2022 ACM.

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

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
EATCS: European Association for Theoretical Computer Science

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 July 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

DST/SERB MATRICS
National Science Foundation
DST/SERB VAJRA visiting faculty scheme
Centre of Excellence in Cryptography Cybersecurity and Distributed Trust under the IIT Madras Institute of Eminence Scheme
U.S.-Israel Binational Science Foundation (BSF)

Conference

SPAA '22

Sponsor:

SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures

July 11 - 14, 2022

PA, Philadelphia, USA

Acceptance Rates

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

Upcoming Conference

SPAA '25

Sponsor:
sigact
sigact

37th ACM Symposium on Parallelism in Algorithms and Architectures

July 28 - August 1, 2025

Portland , OR , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
568
Total Downloads

Downloads (Last 12 months)266
Downloads (Last 6 weeks)42

Reflects downloads up to 05 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Abassi RRiahla MTamine KGoumiri S(2024)Towards a Formal MultipathP2P ProtocolInternational Journal of Business Data Communications and Networking10.4018/IJBDCN.34441619:1(1-13)Online publication date: 21-Jun-2024
https://dl.acm.org/doi/10.4018/IJBDCN.344416
Król MAscigil ORene SSonnino APigaglio MSadre RLange FRivière E(2024)DISC-NG: Robust Service Discovery in the Ethereum Global Network2024 IEEE 9th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP60621.2024.00019(193-215)Online publication date: 8-Jul-2024
https://doi.org/10.1109/EuroSP60621.2024.00019
Tseng LAmbarapu LAloqaily M(2024)NC-DHT: a Robust and Anonymous DHT for Blockchain Systems2024 6th International Conference on Blockchain Computing and Applications (BCCA)10.1109/BCCA62388.2024.10844445(394-399)Online publication date: 26-Nov-2024
https://doi.org/10.1109/BCCA62388.2024.10844445
Xue BMao YVenkatakrishnan SKannan S(2023)Goldfish: Peer Selection using Matrix Completion in Unstructured P2P Network2023 IEEE International Conference on Blockchain and Cryptocurrency (ICBC)10.1109/ICBC56567.2023.10174871(1-9)Online publication date: 1-May-2023
https://doi.org/10.1109/ICBC56567.2023.10174871
Augustine JBhat WNair S(2022)Plateau: A Secure and Scalable Overlay Network for Large Distributed Trust ApplicationsStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-21017-4_5(69-83)Online publication date: 15-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-21017-4_5

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten