Commensal cuckoo
Authors:
Open Access
- 16 February 2012
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGOPS Operating Systems Review
- Vol. 46 (1) , 33-39
Abstract
We present commensal cuckoo,* a secure group partitioning scheme for large-scale systems that maintains the correctness of many small groups, despite a Byzantine adversary that controls a constant (global) fraction of all nodes. In particular, the adversary is allowed to repeatedly rejoin faulty nodes to the system in an arbitrary adaptive manner, e.g., to collocate them in the same group. Commensal cuckoo addresses serious practical limitations of the state-ofthe- art scheme, the cuckoo rule of Awerbuch and Scheideler, tolerating 32x--41x more faulty nodes with groups as small as 64 nodes (as compared to the hundreds required by the cuckoo rule). Secure group partitioning is a key component of highly-scalable, reliable systems such as Byzantine faulttolerant distributed hash tables (DHTs).Keywords
This publication has 26 references indexed in Scilit:
- Robust random number generation for peer-to-peer systemsTheoretical Computer Science, 2009
- Reducing communication costs in robust peer-to-peer networksInformation Processing Letters, 2008
- Novel architectures for P2P applicationsACM Transactions on Algorithms, 2007
- FirefliesACM SIGOPS Operating Systems Review, 2006
- Making Chord Robust to Byzantine Attacks2005
- Group Spreading: A Protocol for Provably Secure Distributed Name Service2004
- Asymptotically Efficient Approaches to Fault-Tolerance in Peer-to-Peer Networks2003
- Kelips: Building an Efficient and Stable P2P DHT through Increased Memory and Background Overhead2003
- Implementing fault-tolerant services using the state machine approach: a tutorialACM Computing Surveys, 1990
- Verifiable secret sharing and multiparty protocols with honest majority1989