{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:35:46Z","timestamp":1767339346752,"version":"3.37.0"},"reference-count":44,"publisher":"Elsevier BV","issue":"13","license":[{"start":{"date-parts":[[2009,8,1]],"date-time":"2009-08-01T00:00:00Z","timestamp":1249084800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computer Networks"],"published-print":{"date-parts":[[2009,8]]},"DOI":"10.1016\/j.comnet.2009.03.008","type":"journal-article","created":{"date-parts":[[2009,3,27]],"date-time":"2009-03-27T10:42:56Z","timestamp":1238150576000},"page":"2340-2359","source":"Crossref","is-referenced-by-count":56,"title":["Brahms: Byzantine resilient random membership sampling"],"prefix":"10.1016","volume":"53","author":[{"given":"Edward","family":"Bortnikov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maxim","family":"Gurevich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Idit","family":"Keidar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriel","family":"Kliot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Shraer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/j.comnet.2009.03.008_bib1","doi-asserted-by":"crossref","unstructured":"A. Allavena, A. Demers, J.E. Hopcroft, Correctness of a gossip based membership protocol, in: ACM PODC, 2005, pp. 292\u2013301.","DOI":"10.1145\/1073814.1073871"},{"key":"10.1016\/j.comnet.2009.03.008_bib2","doi-asserted-by":"crossref","unstructured":"N. Alon, Y. Matias, M. Szegedy, The space complexity of approximating the frequency moments, in: Proc. of the 28th Annual ACM Symposium on Theory of Computing (STOC), 1996, pp. 20\u201329.","DOI":"10.1145\/237814.237823"},{"year":"2004","series-title":"Distributed Computing Fundamentals, Simulations, and Advanced Topics","author":"Attiya","key":"10.1016\/j.comnet.2009.03.008_bib3"},{"key":"10.1016\/j.comnet.2009.03.008_bib4","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, C. Scheideler, Group spreading: a protocol for provably secure distributed name service, in: ICALP, 2004, pp. 183\u2013195.","DOI":"10.1007\/978-3-540-27836-8_18"},{"key":"10.1016\/j.comnet.2009.03.008_bib5","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, C. Scheideler, Robust random number generation for peer-to-peer systems, in: OPODIS, 2006, pp. 275\u2013289.","DOI":"10.1007\/11945529_20"},{"key":"10.1016\/j.comnet.2009.03.008_bib6","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, C. Scheideler, Towards a scalable and robust DHT, in: SPAA, 2006, pp. 318\u2013327.","DOI":"10.1145\/1148109.1148163"},{"key":"10.1016\/j.comnet.2009.03.008_bib7","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, C. Scheideler, Towards scalable and robust overlay networks, in: IPTPS, 2006.","DOI":"10.1145\/1148109.1148163"},{"key":"10.1016\/j.comnet.2009.03.008_bib8","unstructured":"B. Babcock, M. Datar, R. Motwani, Sampling from a moving window over streaming data, in: Proc. of the 13th annual ACM-SIAM symposium on Discrete algorithms (SODA), 2002, pp. 633\u2013634."},{"key":"10.1016\/j.comnet.2009.03.008_bib9","doi-asserted-by":"crossref","unstructured":"G. Badishi, I. Keidar, A. Sasson, Exposing and eliminating vulnerabilities to denial of service attacks in secure gossip-based multicast, in: DSN, June\u2013July 2004, pp. 201\u2013210.","DOI":"10.1109\/DSN.2004.1311892"},{"key":"10.1016\/j.comnet.2009.03.008_bib10","doi-asserted-by":"crossref","unstructured":"Z. Bar-Yossef, R. Friedman, G. Kliot, RaWMS \u2013 random walk based lightweight membership service for wireless ad hoc networks, in: ACM MobiHoc, 2006, pp. 238\u2013249.","DOI":"10.1145\/1132905.1132932"},{"key":"10.1016\/j.comnet.2009.03.008_bib11","doi-asserted-by":"crossref","unstructured":"Z. Bar-Yossef, M. Gurevich, Random sampling from a search engine\u2019s index, in: Proc. of 15th WWW, 2006, pp. 367\u2013376, Full version available as CCIT Report #598, Department of Electrical Engineering, Technion.","DOI":"10.1145\/1135777.1135833"},{"key":"10.1016\/j.comnet.2009.03.008_bib12","doi-asserted-by":"crossref","unstructured":"Z. Bar-Yossef, T.S. Jayram, R. Kumar, D. Sivakumar, L. Trevisan, Counting distinct elements in a data stream, in: Proc. of the Sixth International Workshop on Randomization and Approximation Techniques (RANDOM), 2002, pp. 1\u201310.","DOI":"10.1007\/3-540-45726-7_1"},{"issue":"2","key":"10.1016\/j.comnet.2009.03.008_bib13","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1145\/312203.312207","article-title":"Bimodal multicast","volume":"17","author":"Birman","year":"1999","journal-title":"ACM Trans. Comput. Syst."},{"issue":"3","key":"10.1016\/j.comnet.2009.03.008_bib14","doi-asserted-by":"crossref","first-page":"630","DOI":"10.1006\/jcss.1999.1690","article-title":"Min-wise independent permutations","volume":"60","author":"Broder","year":"2000","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.comnet.2009.03.008_bib15","doi-asserted-by":"crossref","unstructured":"M. Castro, P. Druschel, A.J. Ganesh, A.I.T. Rowstron, D.S. Wallach, Secure routing for structured peer-to-peer overlay networks, in: OSDI, 2002.","DOI":"10.1145\/1060289.1060317"},{"key":"10.1016\/j.comnet.2009.03.008_bib16","unstructured":"T. Condie, V. Kacholia, S. Sankararaman, J. Hellerstein, P. Maniatis, Induced churn as shelter from routing-table poisoning, in: Proc. of the 13th Annual Network and Distributed System Security Symposium (NDSS), 2006."},{"issue":"6","key":"10.1016\/j.comnet.2009.03.008_bib17","doi-asserted-by":"crossref","first-page":"1794","DOI":"10.1137\/S0097539701398363","article-title":"Maintaining Stream Statistics over Sliding Windows","volume":"31","author":"Datar","year":"2002","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.comnet.2009.03.008_bib18","doi-asserted-by":"crossref","unstructured":"A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, D. Terry. epidemic algorithms for replicated database management, in: ACM PODC, August 1987, pp. 1\u201312.","DOI":"10.1145\/41840.41841"},{"key":"10.1016\/j.comnet.2009.03.008_bib19","doi-asserted-by":"crossref","unstructured":"D. Malkhi, Y. Mansour, M. K. Reiter, On diffusing updates in a Byzantine environment, in: SRDS, 1999, pp. 134\u2013143.","DOI":"10.1109\/RELDIS.1999.805090"},{"key":"10.1016\/j.comnet.2009.03.008_bib20","doi-asserted-by":"crossref","unstructured":"J.R. Douceur, The Sybil attack, in: Proc. of the First International Workshop on Peer-to-Peer Systems (IPTPS), 2002, pp. 251\u2013260.","DOI":"10.1007\/3-540-45748-8_24"},{"issue":"4","key":"10.1016\/j.comnet.2009.03.008_bib21","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/945506.945507","article-title":"Lightweight probabilistic broadcast","volume":"21","author":"Eugster","year":"2003","journal-title":"ACM Trans. Comput. Syst. (TOCS)"},{"issue":"2","key":"10.1016\/j.comnet.2009.03.008_bib22","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1109\/TC.2003.1176982","article-title":"Peer-to-Peer membership management for gossip-based protocols","volume":"52","author":"Ganesh","year":"2003","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/j.comnet.2009.03.008_bib23","unstructured":"C. Gkantsidis, M. Mihail, A. Saberi, Random walks in peer-to-peer networks, in: IEEE INFOCOM, 2004, pp. 130\u2013140."},{"issue":"4","key":"10.1016\/j.comnet.2009.03.008_bib24","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1145\/6490.6503","article-title":"How to construct random functions","volume":"33","author":"Goldreich","year":"1986","journal-title":"JACM"},{"key":"10.1016\/j.comnet.2009.03.008_bib25","doi-asserted-by":"crossref","first-page":"167","DOI":"10.2307\/2689700","article-title":"A generalization of Krasnoselski\u2019s theorem on the real line","volume":"48","author":"Hillam","year":"1975","journal-title":"Math. Mag."},{"issue":"3","key":"10.1016\/j.comnet.2009.03.008_bib26","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1145\/1275517.1275520","article-title":"Gossip-based peer sampling","volume":"25","author":"Jelasity","year":"2007","journal-title":"ACM Trans. Comput. Syst. (TOCS)"},{"key":"10.1016\/j.comnet.2009.03.008_bib27","doi-asserted-by":"crossref","unstructured":"G.-P. Jesi, M. van Steen, D. Hales, Identifying malicious peers before it\u2019s too late: a decentralized secure peer sampling service, in: Proc. of the First IEEE International Conference on Self-adaptive and Self-organizing Systems (SASO), June 2007.","DOI":"10.1109\/SASO.2007.32"},{"key":"10.1016\/j.comnet.2009.03.008_bib28","doi-asserted-by":"crossref","unstructured":"H. Johansen, A. Allavena, R. van Renesse, Fireflies: scalable support for intrusion-tolerant network overlays, in: Proc. of the 2006 EuroSys Conference (EuroSys), 2006, pp. 3\u201313.","DOI":"10.1145\/1217935.1217937"},{"key":"10.1016\/j.comnet.2009.03.008_bib29","doi-asserted-by":"crossref","unstructured":"D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin, R. Panigrahy, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the world wide web, in: Proc. of the ACM STOC, 1997, pp. 654\u2013663.","DOI":"10.1145\/258533.258660"},{"key":"10.1016\/j.comnet.2009.03.008_bib30","doi-asserted-by":"crossref","unstructured":"D.R. Karger, M. Ruhl, Simple efficient load balancing algorithms for peer-to-peer systems, in: SPAA, 2004, pp. 36\u201343.","DOI":"10.1145\/1007912.1007919"},{"key":"10.1016\/j.comnet.2009.03.008_bib31","doi-asserted-by":"crossref","unstructured":"V. King, J. Saia, Choosing a random peer, in: ACM PODC, 2004, pp. 125\u2013130.","DOI":"10.1145\/1011767.1011786"},{"key":"10.1016\/j.comnet.2009.03.008_bib32","doi-asserted-by":"crossref","unstructured":"C. Law, K. Siu, Distributed construction of random expander networks, in: IEEE INFOCOM, April 2003, pp. 2133\u20132143.","DOI":"10.1109\/INFCOM.2003.1209234"},{"key":"10.1016\/j.comnet.2009.03.008_bib33","unstructured":"H.C. Li, A. Clement, E.L. Wong, J. Napper, I. Roy, L. Alvisi, M. Dahlin, BAR gossip, in: Proc. of the Seventh USENIX Symp. on Oper. Systems Design and Impl. (OSDI), November 2006, pp. 45\u201358."},{"key":"10.1016\/j.comnet.2009.03.008_bib34","doi-asserted-by":"crossref","unstructured":"C. Lv, P. Cao, E. Cohen, K. Li, S. Shenker, Search and replication in unstructured peer-to-peer networks, in: Proc. of the 16th Intr. Conference on Supercomputing (ICS), 2002, pp. 84\u201395.","DOI":"10.1145\/514203.514206"},{"key":"10.1016\/j.comnet.2009.03.008_bib35","unstructured":"G. Manku, M. Bawa, P. Raghavan, Symphony: distributed hashing in a small world, in: Proc. of the Fourth USENIX Symposium on Internet Technologies and Systems (USITS), 2003."},{"key":"10.1016\/j.comnet.2009.03.008_bib36","doi-asserted-by":"crossref","unstructured":"L. Massoulie, E. Le Merrer, A.-M. Kermarrec, A.J. Ganesh, Peer counting and sampling in overlay networks: random walk methods, in: ACM PODC, 2006, pp. 123\u2013132.","DOI":"10.1145\/1146381.1146402"},{"key":"10.1016\/j.comnet.2009.03.008_bib37","doi-asserted-by":"crossref","unstructured":"R. Melamed, I. Keidar, Araneola: a scalable reliable multicast system for dynamic environments, in: IEEE NCA, 2004, pp. 5\u201314.","DOI":"10.1109\/NCA.2004.1347755"},{"key":"10.1016\/j.comnet.2009.03.008_bib38","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1145\/359460.359473","article-title":"Secure communications over insecure channels","volume":"21","author":"Merkle","year":"1978","journal-title":"CACM"},{"issue":"1","key":"10.1016\/j.comnet.2009.03.008_bib39","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/s00446-002-0082-4","article-title":"Tolerating malicious gossip","volume":"16","author":"Minsky","year":"2003","journal-title":"Dist. Comput."},{"key":"10.1016\/j.comnet.2009.03.008_bib40","doi-asserted-by":"crossref","unstructured":"A. Singh, M. Castro, P. Druschel, A. Rowstron, Defending against eclipse attacks on overlay networks, in: ACM SIGOPS European Workshop, 2004.","DOI":"10.1145\/1133572.1133613"},{"key":"10.1016\/j.comnet.2009.03.008_bib41","doi-asserted-by":"crossref","unstructured":"A. Singh, T.-W. Ngan, P. Druschel, D.S. Wallach, Eclipse attacks on overlay networks: threats and defenses, in: IEEE INFOCOM, 2006.","DOI":"10.1109\/INFOCOM.2006.231"},{"issue":"1","key":"10.1016\/j.comnet.2009.03.008_bib42","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1145\/3147.3165","article-title":"Random sampling with a reservoir","volume":"11","author":"Vitter","year":"1985","journal-title":"ACM Trans. Math. Softw."},{"issue":"2","key":"10.1016\/j.comnet.2009.03.008_bib43","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/s10922-005-4441-x","article-title":"CYCLON: inexpensive membership management for unstructured P2P overlays","volume":"13","author":"Voulgaris","year":"2005","journal-title":"J. Netw. Syst. Manage."},{"issue":"3","key":"10.1016\/j.comnet.2009.03.008_bib44","doi-asserted-by":"crossref","first-page":"576","DOI":"10.1109\/TNET.2008.923723","article-title":"SybilGuard: defending against Sybil attacks via social networks","volume":"16","author":"Yu","year":"2008","journal-title":"IEEE\/ACM Trans. Netw. (ToN)"}],"container-title":["Computer Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.elsevier.com\/content\/article\/PII:S1389128609001182?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.elsevier.com\/content\/article\/PII:S1389128609001182?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T18:41:19Z","timestamp":1739040079000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/linkinghub.elsevier.com\/retrieve\/pii\/S1389128609001182"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":44,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["S1389128609001182"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/j.comnet.2009.03.008","relation":{},"ISSN":["1389-1286"],"issn-type":[{"type":"print","value":"1389-1286"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}