Brahms: byzantine resilient random membership sampling Export

@inproceedings{citeulike:3736630, 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.}, address = {New York, NY, USA}, author = {Bortnikov, Edward and Gurevich, Maxim and Keidar, Idit and Kliot, Gabriel and Shraer, Alexander}, booktitle = {PODC '08: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing}, citeulike-article-id = {3736630}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1400751.1400772}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1400751.1400772}, doi = {10.1145/1400751.1400772}, isbn = {978-1-59593-989-0}, keywords = {byzantine-fault, gossip, lecture-pap, project-p2p-theory}, location = {Toronto, Canada}, pages = {145--154}, posted-at = {2008-12-02 18:23:29}, priority = {1}, publisher = {ACM}, title = {Brahms: byzantine resilient random membership sampling}, url = {http://dx.doi.org/10.1145/1400751.1400772}, year = {2008} }

TY - CONF ID - citeulike:3736630 L3 - citeulike-article-id:3736630 N2 - 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. CY - Toronto, Canada SN - 978-1-59593-989-0 AD - New York, NY, USA EP - 154 TI - Brahms: byzantine resilient random membership sampling PB - ACM T2 - PODC '08: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing SP - 145 KW - byzantine-fault KW - gossip KW - lecture-pap KW - project-p2p-theory AU - Bortnikov, Edward AU - Gurevich, Maxim AU - Keidar, Idit AU - Kliot, Gabriel AU - Shraer, Alexander PY - 2008/// UR - http://dx.doi.org/10.1145/1400751.1400772 ER -