Commensal cuckoo: Secure group partitioning for large-scale services

We present commensal cuckoo, a secure group partition- ing scheme for large-scale systems that maintains the cor- rectness of many small groups, despite a Byzantine adver- sary 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 man- ner, e.g., to collocate them in the same group. Commensal cuckoo addresses serious practical limitations of the state-of- the-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 fault- tolerant distributed hash tables (DHTs).