We present an efficient lock-free algorithm for parallel accessible hash tables with open addressing, which promises more
robust performance and reliability than conventional lock-based implementations. "Lock-free" means that it is guaranteed that
always at least one process completes its operation within a bounded number of steps. For a single processor architecture
our solution is as efficient as sequential hash tables. On a multiprocessor architecture this is also the case when all processors
have comparable speeds. The algorithm allows processors that have widely different speeds or come to a halt. It can easily
be implemented using C-like languages and requires on average only constant time for insertion, deletion or accessing of elements.
The algorithm allows the hash tables to grow and shrink when needed.
Lock-free algorithms are hard to design correctly, even when apparently straightforward. Ensuring the correctness of the design
at the earliest possible stage is a major challenge in any responsible system development. In view of the complexity of the
algorithm, we turned to the interactive theorem prover PVS for mechanical support. We employ standard deductive verification
techniques to prove around 200 invariance properties of our algorithm, and describe how this is achieved with the theorem
prover PVS.
CR Subject Classification (1991): D.1 Programming techniques
AMS Subject Classification (1991): 68Q22 Distributed algorithms, 68P20 Information storage and retrieval
Keywords: Hash tables - Distributed algorithms - Lock-free - Wait-free
Received: 13 April 2004, Accepted: 27 October 2004, Published online: 25 November 2004