Brahms: byzantine resilient random membership sampling

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: André Allavena , Alan Demers , John E. Hopcroft, Correctness of a gossip based membership protocol, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073871]
• 2: Hagit Attiya , Jennifer Welch, Distributed Computing: Fundamentals, Simulations and Advanced Topics, John Wiley & Sons, 2004
• 3: Baruch Awerbuch , Christian Scheideler, Towards a scalable and robust DHT, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148163]
• 4: Gal Badishi , Idit Keidar , Amir Sasson, Exposing and Eliminating Vulnerabilities to Denial of Service Attacks in Secure Gossip-Based Multicast, Proceedings of the 2004 International Conference on Dependable Systems and Networks, p.223, June 28-July 01, 2004
• 5: Ziv Bar-Yossef , Roy Friedman , Gabriel Kliot, RaWMS -: random walk based lightweight membership service for wireless ad hoc network, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132932]
• 6: Kenneth P. Birman , Mark Hayden , Oznur Ozkasap , Zhen Xiao , Mihai Budiu , Yaron Minsky, Bimodal multicast, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.41-88, May 1999 [doi>10.1145/312203.312207]
• 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: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations, Journal of Computer and System Sciences, v.60 n.3, p.630-659, June 2000 [doi>10.1006/jcss.1999.1690]
• 9: T. Condie, V. Kacholia, S. Sankararaman, J. Hellerstein, and P. Maniatis. Induced Churn as Shelter from RoutingTable Poisoning. In NDSS, 2006.
• 10: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 11: Dahlia Malkhi , Yishay Mansour , Michael K. Reiter, On Diffusing Updates in a Byzantine Environment, Proceedings of the 18th IEEE Symposium on Reliable Distributed Systems, p.134, October 18-21, 1999
• 12: John R. Douceur, The Sybil Attack, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.251-260, March 07-08, 2002
• 13: P. Th. Eugster , R. Guerraoui , S. B. Handurukande , P. Kouznetsov , A.-M. Kermarrec, Lightweight probabilistic broadcast, ACM Transactions on Computer Systems (TOCS), v.21 n.4, p.341-374, November 2003 [doi>10.1145/945506.945507]
• 14: Ayalvadi J. Ganesh , Anne-Marie Kermarrec , Laurent Massoulié, Peer-to-Peer Membership Management for Gossip-Based Protocols, IEEE Transactions on Computers, v.52 n.2, p.139-149, February 2003 [doi>10.1109/TC.2003.1176982]
• 15: C. Gkantsidis, M. Mihail, and A. Saberi. Random walks in peer-to-peer networks. In IEEE INFOCOM, 2004.
• 16: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 17: B. P. Hillam. A Generalization of Krasnoselski's Theorem on the Real Line. Math. Mag., 48:167--168, 1975.
• 18: Márk Jelasity , Spyros Voulgaris , Rachid Guerraoui , Anne-Marie Kermarrec , Maarten van Steen, Gossip-based peer sampling, ACM Transactions on Computer Systems (TOCS), v.25 n.3, p.8-es, August 2007 [doi>10.1145/1275517.1275520]
• 19: Håvard Johansen , André Allavena , Robbert van Renesse, Fireflies: scalable support for intrusion-tolerant network overlays, Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006, April 18-21, 2006, Leuven, Belgium
• 20: Valerie King , Jared Saia, Choosing a random peer, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011786]
• 21: C. Law and K. Siu. Distributed construction of random expander networks. In IEEE INFOCOM, April 2003.
• 22: Harry C. Li , Allen Clement , Edmund L. Wong , Jeff Napper , Indrajit Roy , Lorenzo Alvisi , Michael Dahlin, BAR Gossip, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, p.14-14, November 06-08, 2006, Seattle, WA
• 23: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
• 24: Gurmeet Singh Manku , Mayank Bawa , Prabhakar Raghavan, Symphony: distributed hashing in a small world, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.10-10, March 26-28, 2003, Seattle, WA
• 25: Laurent Massoulié , Erwan Le Merrer , Anne-Marie Kermarrec , Ayalvadi Ganesh, Peer counting and sampling in overlay networks: random walk methods, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146402]
• 26: Roie Melamed , Idit Keidar, Araneola: A Scalable Reliable Multicast System for Dynamic Environments, Proceedings of the Network Computing and Applications, Third IEEE International Symposium, p.5-14, August 30-September 01, 2004
• 27: Ralph C. Merkle, Secure communications over insecure channels, Communications of the ACM, v.21 n.4, p.294-299, April 1978 [doi>10.1145/359460.359473]
• 28: Yaron M. Minsky , Fred B. Schneider, Tolerating malicious gossip, Distributed Computing, v.16 n.1, p.49-68, February 2003 [doi>10.1007/s00446-002-0082-4]
• 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.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

General Terms:
Algorithms, Reliability, Theory

Keywords:
byzantine faults, gossip, membership, random sampling