Achieving heterogeneity and fairness in Kademlia

Attempts to construct overlay networks in ubiquitous networked environments will face challenges of both performance and resource heterogeneity. We describe enhancements to Kademlia, a peer-to-peer system which has provable consistency and performance in a fault-prone environment. Our enhancements can accommodate nodes with arbitrary degree of heterogeneity, while at the same time ensuring fairness, without adding much overhead. A probabilistic mechanism to check parameter integrity is introduced, which in turn is exploited to probabilistically check compliance of nodes to advertised parameters. To demonstrate the feasibility of this approach, we have implemented a prototype and then evaluated its ability to accommodate arbitrary degree of heterogeneity.