REIK: A Novel P2P Overlay Network with Byzantine Fault Tolerance

Byzantine faults in a peer-to-peer (P2P) system are re- sulted from adversarial and inconsistent peer behaviors. Faulty peers can disrupt the routing functions in the peer joining and lookup schemes. Byzantine attackers may col- lude with each other to paralyze the entire P2P network op- erations. We discover a novel DHT-based overlay networks (REIK) with Byzantine fault tolerance. REIK based on a ring which embeds an inverse Kautz digraph IK(d, m), to enable multi-path P2P routing. The inverse Kautz network provides multiple entry points and multiple routes between node pair. The REIK overlay is the first constant degree and O(log n) diameter DHT scheme with constant congestion and Byzantine fault tolerance. For large d 2, the REIK overlays handle random and Byzantine faults effectively, far beyond the capability of Chord and CAN.