skip to main content
10.1145/1400751.1400772acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
research-article

Brahms: byzantine resilient random membership sampling

Published: 18 August 2008 Publication History

Abstract

We present Brahms, an algorithm for sampling random nodes in a large dynamic system prone to malicious behavior. Brahms stores small membership views at each node, and yet overcomes Byzantine attacks by a linear portion of the system. Brahms is composed of two components. The first one is a resilient gossip-based membership protocol. The second one uses a novel memory-efficient approach for uniform sampling from a possibly biased stream of ids that traverse the node. We evaluate Brahms using rigorous analysis, backed by simulations, which show that our theoretical model captures the protocol's essentials. We study two representative attacks, and show that with high probability, an attacker cannot create a partition between correct nodes. We further prove that each node's sample converges to a uniform one over time. To our knowledge, no such properties were proven for gossip protocols in the past.

References

[1]
A. Allavena, A. Demers, and J. E. Hopcroft. Correctness of a gossip based membership protocol. In ACM PODC, pages 292--301, 2005.
[2]
H. Attiya and J. Welch. Distributed Computing Fundamentals, Simulations, and Advanced Topics. John Wiley and Sons, Inc., 2004.
[3]
B. Awerbuch and C. Scheideler. Towards a Scalable and Robust DHT. In SPAA, pages 318--327, 2006.
[4]
G. Badishi, I. Keidar, and A. Sasson. Exposing and Eliminating Vulnerabilities to Denial of Service Attacks in Secure Gossip-Based Multicast. In DSN, pages 201--210, June -- July 2004.
[5]
Z. Bar-Yossef, R. Friedman, and G. Kliot. RaWMS - Random Walk based Lightweight Membership Service for Wireless Ad Hoc Networks. In ACM MobiHoc, pages 238--249, 2006.
[6]
K. P. Birman, M. Hayden, O. Ozkasap, Z. Xiao, M. Budiu, and Y. Minsky. Bimodal multicast. ACM Transactions on Computer Systems, 17(2):41--88, 1999.
[7]
E. Bortnikov, M. Gurevich, I. Keidar, G. Kliot, and A. Shraer. Brahms: Byzantine Resilient Random Membership Sampling. Technical Report CCIT Report #688, Technion, Feb 2008.
[8]
A. Z. Broder, M. Charikar, A. M. Frieze, and M. Mitzenmacher. Min-wise independent permutations. J. Computer and System Sciences, 60(3):630--659, 2000.
[9]
T. Condie, V. Kacholia, S. Sankararaman, J. Hellerstein, and P. Maniatis. Induced Churn as Shelter from RoutingTable Poisoning. In NDSS, 2006.
[10]
A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry. Epidemic Algorithms for Replicated Database Management. In ACM PODC, pages 1--12, August 1987.
[11]
D.Malkhi, Y. Mansour, and M. K. Reiter. On Diffusing Updates in a Byzantine Environment. In SRDS, pages 134--143, 1999.
[12]
J.R. Douceur. The Sybil Attack. In IPTPS, 2002.
[13]
P. Th. Eugster, R. Guerraoui, S. B. Handurukande, P. Kouznetsov, and A.-M. Kermarrec. Lightweight probabilistic broadcast. ACM Transactions on Computer Systems (TOCS), 21(4):341--374, 2003.
[14]
A. J. Ganesh, A.-M. Kermarrec, and L. Massoulie. Peer-to-Peer Membership Management for Gossip-Based Protocols. IEEE Trans. Comput., 52(2):139--149, 2003.
[15]
C. Gkantsidis, M. Mihail, and A. Saberi. Random walks in peer-to-peer networks. In IEEE INFOCOM, 2004.
[16]
O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. JACM, 33(4):792--807, 1986.
[17]
B. P. Hillam. A Generalization of Krasnoselski's Theorem on the Real Line. Math. Mag., 48:167--168, 1975.
[18]
M. Jelasity, S. Voulgaris, R. Guerraoui, A.-M. Kermarrec, and M. van Steen. Gossip-based peer sampling. ACM TOCS, 25(3):8, 2007.
[19]
H. Johansen, A. Allavena, and R. van Renesse. Fireflies: scalable support for intrusion-tolerant network overlays. In Proc. of the 2006 EuroSys conference (EuroSys), pages 3--13, 2006.
[20]
V. King and J. Saia. Choosing a random peer. In ACM PODC, pages 125--130, 2004.
[21]
C. Law and K. Siu. Distributed construction of random expander networks. In IEEE INFOCOM, April 2003.
[22]
H. C. Li, A. Clement, E. L. Wong, J. Napper, I. Roy, L. Alvisi, and M. Dahlin. BAR Gossip. In Proc. of the 7th USENIX Symp. on Oper. Systems Design and Impl. (OSDI), pages 45--58, Nov. 2006.
[23]
C. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker. Search and replication in unstructured peer-to-peer networks. In Proc. of the 16th Intr. Conference on Supercomputing (ICS), pages 84--95, 2002.
[24]
G. Manku, M. Bawa, and P. Raghavan. Symphony: Distributed hashing in a small world. In Proc. of the 4th USENIX Symposium on Internet Technologies and Systems (USITS), 2003.
[25]
L. Massoulie, E. Le Merrer, A.-M. Kermarrec, and A. J. Ganesh. Peer Counting and Sampling in Overlay Networks: Random Walk Methods. In ACM PODC, pages 123--132, 2006.
[26]
R. Melamed and I. Keidar. Araneola: A Scalable Reliable Multicast System for Dynamic Environments. In IEEE NCA, pages 5--14, 2004.
[27]
R. C. Merkle. Secure Communications over Insecure Channels. CACM, 21:294--299, April 1978.
[28]
Y. M. Minsky and F. B. Schneider. Tolerating Malicious Gossip. Dist. Computing, 16(1):49--68, February 2003.
[29]
Atul Singh, T.-W. Ngan, Peter Druschel, and Dan S. Wallach. Eclipse Attacks on Overlay Networks: Threats and Defenses. In IEEE INFOCOM, 2006.
[30]
S. Voulgaris, D. Gavidia, and M. van Steen. CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays. Journal of Network and Systems Management, 13(2):197--217, July 2005.

Cited By

View all
  • (2024)Peerswap: A Peer-Sampler with Randomness Guarantees2024 43rd International Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS64841.2024.00034(271-281)Online publication date: 30-Sep-2024
  • (2023)Reducing Latency of DAG-based Consensus in the Asynchronous Setting via the UTXO Model2023 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom)10.1109/ISPA-BDCloud-SocialCom-SustainCom59178.2023.00071(294-304)Online publication date: 21-Dec-2023
  • (2023)AccountNet: Accountable Data Propagation Using Verifiable Peer Shuffling2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS57875.2023.00050(48-61)Online publication date: Jul-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '08: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing
August 2008
474 pages
ISBN:9781595939890
DOI:10.1145/1400751
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: 18 August 2008

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. byzantine faults
  2. gossip
  3. membership
  4. random sampling

Qualifiers

  • Research-article

Conference

PODC '08

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)31
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Peerswap: A Peer-Sampler with Randomness Guarantees2024 43rd International Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS64841.2024.00034(271-281)Online publication date: 30-Sep-2024
  • (2023)Reducing Latency of DAG-based Consensus in the Asynchronous Setting via the UTXO Model2023 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom)10.1109/ISPA-BDCloud-SocialCom-SustainCom59178.2023.00071(294-304)Online publication date: 21-Dec-2023
  • (2023)AccountNet: Accountable Data Propagation Using Verifiable Peer Shuffling2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS57875.2023.00050(48-61)Online publication date: Jul-2023
  • (2023)SecureCyclon: Dependable Peer Sampling2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS57875.2023.00041(1-12)Online publication date: Jul-2023
  • (2022)Gossiping for Communication-Efficient BroadcastAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15982-4_15(439-469)Online publication date: 12-Oct-2022
  • (2019)Fast Fault-Tolerant Sampling via Random Walk in Dynamic Networks2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS.2019.00060(536-544)Online publication date: Jul-2019
  • (2016)Error Detector Placement for Soft Computing ApplicationsACM Transactions on Embedded Computing Systems10.1145/280115415:1(1-25)Online publication date: 13-Jan-2016
  • (2016)CUDA LeaksACM Transactions on Embedded Computing Systems10.1145/280115315:1(1-25)Online publication date: 13-Jan-2016
  • (2016)A Probabilistic Gossip-based Secure Protocol for Unstructured P2P NetworksProcedia Computer Science10.1016/j.procs.2016.02.12278:C(595-602)Online publication date: 1-Mar-2016
  • (2015)Smart data pricingCommunications of the ACM10.1145/275654358:12(86-93)Online publication date: 23-Nov-2015
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media