This is joint work with Gao Hui (then at Groningen University, currently at the University of Electronic Science and Technology of China, Chengdu) and Jan Friso Groote (Eindhoven University of Technology). It concerns our papers:
In multiprogrammed systems, synchronization often turns out to be a performance bottleneck and the source of poor fault-tolerance. Wait-free and lock-free algorithms can do without locking mechanisms, and therefore do not suffer from these problems. In the paper, we present an efficient lock-free algorithm for parallel accessible hash tables, which promises more robust performance and reliability than conventional lock-based implementations. Our solution is as efficient as sequential hash tables. It can easily be implemented using C-like languages and requires on average only constant time for insertion, deletion or accessing of elements. Apart from that, our new algorithm allows the hash tables to grow and shrink dynamically when needed.
A true problem of lock-free algorithms is that they 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. Our algorithm contains 81 atomic statements. In view of the complexity of the algorithm and its correctness properties, 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 almost wait-free algorithm. All theories in the specification file for our algorithm has been proved by PVS2.4 with its associated proof scripts.
Comments are welcome, 1 October, 2012
Back to my home page.
Wim H. Hesselink, e-mail: w.h.hesselink@rug.nl