Testing implementations of Distributed Hash Tables

Abstract

A lot of research about peer-to-peer systems, today, has been focusing on designing better structured peer-to-peer overlay networks or Distributed Hash Tables, which are simply called DHTs. To our knowledge, not many papers, however, have been published about testing implementations of them. This thesis presents an attempt to test an implementation of Chord, one of the well known DHTs, with a property-based testing method. We propose an abstract state machine as a way to model a DHT, and as a correctness property that its implementation is supposed to satisfy. As a case study, we test the Chord implementation with a property-based random testing tool, showing some faults in the implementation, and suggesting some modifications in its original algorithm.