Scalable Distributed Hash Tables

title:Scalable Distributed Hash Tables
keywords:High-performance computing, distributed, hash tables
topics:Algorithms and Data Structures
contact:W.H.M. Oortwijn MSc & prof.dr. M. Huisman


Description

Hash tables are a central data structure for many different applications, including graph processing and model checking. The scalability of parallel graph processors and model checkers heavily depends on the scalability of their hash tables. This motivated a lot of research on making concurrent hash tables highly scalable, notably [2]. 

In case of distributed model checking and graph processing, a distributed hash table is often used to make use of all the available memory of all participating machines. Here the same principle applies: the scalability of distributed model checkers depends on the scalability of the underlying hash table. However, less research has been performed on making highly scalable distributed hash tables.

This research involves investigating existing implementations of distributed hash tables and designing an improved version that is more scalable. You will implement your hash table on a shared-memory abstraction with support for high-performance networking (e.g. UPC, OpenSHMEM, or MPI), and evaluate its scalability with respect to existing implementations (e.g. Pilaf and Nessie). A good starting point might be [1]. 

References

  1. A Distributed Hash Table for Shared Memory (Digital version available here)
  2. Boosting Multi-Core Reachability Performance with Shared Hash Tables (Digital version available here)