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).