Wim Hendrik Hesselink
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Wim Hendrik Hesselink has a total of 34 co-authors. Here are the top co-authors by number of shared publications:
- Jan Friso Groote
Eindhoven University of Technology
6 shared publications - Peter A. Buhr
Cheriton School of Computer Science University of Waterloo Waterloo Ontario Canada
6 shared publications David Dice
Oracle Labs Burlington MA USA
4 shared publicationsHui Gao
4 shared publications- Alex A. Aravind
Computer Science Program, University of Northern British Columbia, Prince George, Canada
3 shared publications Arnold Meijster
2 shared publications
Latest Publications
- Open Access
- 12 June 2025
- Published by Association for Computing Machinery (ACM) in Formal Aspects of Computing
- Vol. 37 (3) , 1-26
Waitfree Linearization of an Arbitrary Data Object
Waitfree linearization of data objects was introduced by Herlihy in 1991. The present article proposes an algorithm for waitfree linearization of a possibly nondeterministic data object in bounded memory, together with a complete proof of correctness supported by the proof assistant PVS. The project is exceptional in that the proofs of 70 invariants are recorded systematically, and that waitfree progress is quantified in waitfree complexity and is formally proved.
- 12 June 2025
- Published by Association for Computing Machinery (ACM) in Formal Aspects of Computing
- Vol. 37 (3) , 1-26
Open AccessWaitfree Linearization of an Arbitrary Data Object
Waitfree linearization of data objects was introduced by Herlihy in 1991. The present article proposes an algorithm for waitfree linearization of a possibly nondeterministic data object in bounded memory, together with a complete proof of correctness supported by the proof assistant PVS. The project is exceptional in that the proofs of 70 invariants are recorded systematically, and that waitfree progress is quantified in waitfree complexity and is formally proved.
- Open Access
- 8 November 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 11 (4) , 1-20
First-Come-First-Served as a Separate Principle
A lock is a mechanism to guarantee mutual exclusion with eventual progress, i.e., some degree of fairness. First-come-first-served (FCFS) progress is perfectly fair. FCFS progress can be offered by a locking algorithm or added by wrapping a non-FCFS lock with a separate FCFS algorithm. A new separate FCFS algorithm is presented that creates FCFS progress by wrapping a lock’s entry protocol (acquire). The algorithm addresses an important safety issue in locking, called barging, where arriving threads proceed before waiting threads or waiting threads are serviced with some bias. Barging increases latency for waiting threads and is non-intuitive to concurrent programmers, even though it is inherent to non-deterministic concurrent execution. A correctness proof is presented for the new FCFS algorithm and verified with the proof assistant PVS. Experimental tests are performed to ensure the presented wrapper provides FCFS progress when used to transform non-FCFS software and hardware locks. The performance of the non-FCFS and transformed FCFS counterparts is compared and contrasted with locks using inherent FCFS progress. The results show the FCFS transforms are performant for most algorithms, providing an additional tool for application developers to achieve correctness without a significant global performance reduction.
- 8 November 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 11 (4) , 1-20
Open AccessFirst-Come-First-Served as a Separate Principle
A lock is a mechanism to guarantee mutual exclusion with eventual progress, i.e., some degree of fairness. First-come-first-served (FCFS) progress is perfectly fair. FCFS progress can be offered by a locking algorithm or added by wrapping a non-FCFS lock with a separate FCFS algorithm. A new separate FCFS algorithm is presented that creates FCFS progress by wrapping a lock’s entry protocol (acquire). The algorithm addresses an important safety issue in locking, called barging, where arriving threads proceed before waiting threads or waiting threads are serviced with some bias. Barging increases latency for waiting threads and is non-intuitive to concurrent programmers, even though it is inherent to non-deterministic concurrent execution. A correctness proof is presented for the new FCFS algorithm and verified with the proof assistant PVS. Experimental tests are performed to ensure the presented wrapper provides FCFS progress when used to transform non-FCFS software and hardware locks. The performance of the non-FCFS and transformed FCFS counterparts is compared and contrasted with locks using inherent FCFS progress. The results show the FCFS transforms are performant for most algorithms, providing an additional tool for application developers to achieve correctness without a significant global performance reduction.
- Open Access
- 20 June 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 10 (2) , 1-23
MCSH, a Lock with the Standard Interface
The MCS lock of Mellor-Crummey and Scott (1991), 23 pages. is a very efficient first-come first-served mutual-exclusion algorithm that uses the atomic hardware primitives fetch-and-store and compare-and-swap. However, it has the disadvantage that the calling thread must provide a pointer to an allocated record. This additional parameter violates the standard locking interface, which has only the lock as a parameter. Hence, it is impossible to switch to MCS without editing and recompiling an application that uses locks. This article provides a variation of MCS with the standard interface, which remains FCFS, called MCSH. One key ingredient is to stack allocate the necessary record in the acquire procedure of the lock, so its life-time only spans the delay to enter a critical section. A second key ingredient is communicating the allocated record between the acquire and release procedures through the lock to maintain the standard locking interface. Both of these practices are known to practitioners, but our solution combines them in a unique way. Furthermore, when these practices are used in prior papers, their correctness is often argued informally. The correctness of MCSH is verified rigorously with the proof assistant PVS, and experiments are run to compare its performance with MCS and similar locks.
- 20 June 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 10 (2) , 1-23
Open AccessMCSH, a Lock with the Standard Interface
The MCS lock of Mellor-Crummey and Scott (1991), 23 pages. is a very efficient first-come first-served mutual-exclusion algorithm that uses the atomic hardware primitives fetch-and-store and compare-and-swap. However, it has the disadvantage that the calling thread must provide a pointer to an allocated record. This additional parameter violates the standard locking interface, which has only the lock as a parameter. Hence, it is impossible to switch to MCS without editing and recompiling an application that uses locks. This article provides a variation of MCS with the standard interface, which remains FCFS, called MCSH. One key ingredient is to stack allocate the necessary record in the acquire procedure of the lock, so its life-time only spans the delay to enter a critical section. A second key ingredient is communicating the allocated record between the acquire and release procedures through the lock to maintain the standard locking interface. Both of these practices are known to practitioners, but our solution combines them in a unique way. Furthermore, when these practices are used in prior papers, their correctness is often argued informally. The correctness of MCSH is verified rigorously with the proof assistant PVS, and experiments are run to compare its performance with MCS and similar locks.
- Open Access
- 3 January 2022
- Published by Elsevier in Science of Computer Programming
- Vol. 216
Trylock, a case for temporal logic and eternity variables
- 3 January 2022
- Published by Elsevier in Science of Computer Programming
- Vol. 216
Open AccessTrylock, a case for temporal logic and eternity variables
- Open Access
- 10 February 2021
- Published by Association for Computing Machinery (ACM) in Formal Aspects of Computing
- Vol. 33 (2) , 185-205
UNITY and Büchi automata
UNITY is a model for concurrent specifications with a complete logic for proving progress properties of the form “ P leads to Q ”. UNITY is generalized to U-specifications by giving more freedom to specify the steps that are to be taken infinitely often. In particular, these steps can correspond to non-total relations. The generalization keeps the logic sound and complete. The paper exploits the generalization in two ways. Firstly, the logic remains sound when the specification is extended with hypotheses of the form “ F leads to G ”. As the paper shows, this can make the logic incomplete. The generalization is used to show that the logic remains complete, if the added hypotheses “ F leads to G ” satisfy “ F unless G ”. The main result extends the applicability and completeness of UNITY logic to proofs that a given concurrent program satisfies any given formula of LTL, linear temporal logic, without the next-operator which is omitted because it is sensitive to stuttering. For this purpose, the program, written as a UNITY program, is extended with a number of boolean variables. The proof method relies on implementing the LTL formula, i.e., restricting the specification in such a way that only those runs remain that satisfy the formula. This result is a variation of the classical construction of a Büchi automatonfor a given LTL formula that accepts precisely those runs that satisfy the formula.
- 10 February 2021
- Published by Association for Computing Machinery (ACM) in Formal Aspects of Computing
- Vol. 33 (2) , 185-205
Open AccessUNITY and Büchi automata
UNITY is a model for concurrent specifications with a complete logic for proving progress properties of the form “ P leads to Q ”. UNITY is generalized to U-specifications by giving more freedom to specify the steps that are to be taken infinitely often. In particular, these steps can correspond to non-total relations. The generalization keeps the logic sound and complete. The paper exploits the generalization in two ways. Firstly, the logic remains sound when the specification is extended with hypotheses of the form “ F leads to G ”. As the paper shows, this can make the logic incomplete. The generalization is used to show that the logic remains complete, if the added hypotheses “ F leads to G ” satisfy “ F unless G ”. The main result extends the applicability and completeness of UNITY logic to proofs that a given concurrent program satisfies any given formula of LTL, linear temporal logic, without the next-operator which is omitted because it is sensitive to stuttering. For this purpose, the program, written as a UNITY program, is extended with a number of boolean variables. The proof method relies on implementing the LTL formula, i.e., restricting the specification in such a way that only those runs remain that satisfy the formula. This result is a variation of the classical construction of a Büchi automatonfor a given LTL formula that accepts precisely those runs that satisfy the formula.
- Open Access
- 1 July 2019
- Published by Elsevier in Indagationes Mathematicae
- Vol. 30 (4) , 623-648
The nullcone of the Lie algebra of- 1 July 2019
- Published by Elsevier in Indagationes Mathematicae
- Vol. 30 (4) , 623-648
Open AccessThe nullcone of the Lie algebra of - Open Access
- 31 December 2018
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 5 (4) , 1-29
Group Mutual Exclusion by Fetch-and-increment
The group mutual exclusion (GME) problem (also called the room synchronization problem) arises in various practical applications that require concurrent data sharing. Group mutual exclusion aims to achieve exclusive access to a shared resource (a shared room) while facilitating concurrency among non-conflicting requests. The problem is that threads with distinct interests are not allowed to access the shared resource concurrently, but multiple threads with same interest can. In Blelloch et al. (2003), the authors presented a simple solution to the room synchronization problem using fetch8add ( F 8 A ) and test-and-set ( T 8 S ) atomic operations. This algorithm has O ( m ) remote memory references (RMRs) in the cache coherent (CC) model, where m is the number of forums. In Bhatt and Huang (2010), an open problem was posed: “ Is it possible to design a GME algorithm with constant RMR for the CC model using fetch8add instructions? ” This question is partially answered in this article by presenting a group mutual exclusion algorithm using fetch-and-increment instructions. The algorithm is simple and scalable.
- 31 December 2018
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 5 (4) , 1-29
Open AccessGroup Mutual Exclusion by Fetch-and-increment
The group mutual exclusion (GME) problem (also called the room synchronization problem) arises in various practical applications that require concurrent data sharing. Group mutual exclusion aims to achieve exclusive access to a shared resource (a shared room) while facilitating concurrency among non-conflicting requests. The problem is that threads with distinct interests are not allowed to access the shared resource concurrently, but multiple threads with same interest can. In Blelloch et al. (2003), the authors presented a simple solution to the room synchronization problem using fetch8add ( F 8 A ) and test-and-set ( T 8 S ) atomic operations. This algorithm has O ( m ) remote memory references (RMRs) in the cache coherent (CC) model, where m is the number of forums. In Bhatt and Huang (2010), an open problem was posed: “ Is it possible to design a GME algorithm with constant RMR for the CC model using fetch8add instructions? ” This question is partially answered in this article by presenting a group mutual exclusion algorithm using fetch-and-increment instructions. The algorithm is simple and scalable.
- Open Access
- 30 November 2018
- Published by Elsevier in Indagationes Mathematicae
- Vol. 30 (2) , 265-287
Conditionally complete sponges: New results on generalized lattices
- 30 November 2018
- Published by Elsevier in Indagationes Mathematicae
- Vol. 30 (2) , 265-287
Open AccessConditionally complete sponges: New results on generalized lattices
- 17 May 2018
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 30 (18)
High‐contention mutual exclusion by elevator algorithms
Summary: This paper presents new starvation‐free hardware‐assisted and software‐only algorithms for the N‐thread mutual‐exclusion problem. The hardware‐assisted versions use a single atomic‐CAS instruction and no fences. The software‐only algorithms simulate the CAS instruction using a variation of Burns‐Lamport (1 fence) or Lamport's fast algorithm (3 fences). The algorithms are based on Attiya et al, where every thread in the critical section chooses its successor (if one is available). While Attiya et al use a binary tree for this purpose, it can also be done with a linear search. Surprisingly, all software‐only algorithms perform equally well under maximal contention on three different computer architectures; the hardware‐assisted versions perform better under minimal contention. The new algorithms are between −5% to 50% slower for maximal contention than the starvation‐free first‐come first‐served hardware‐assisted MCS algorithm, which uses two atomic instructions (fetch‐store and CAS); they are between 10% to 50% slower than MCS for minimal contention.
- 17 May 2018
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 30 (18)
High‐contention mutual exclusion by elevator algorithms
Summary: This paper presents new starvation‐free hardware‐assisted and software‐only algorithms for the N‐thread mutual‐exclusion problem. The hardware‐assisted versions use a single atomic‐CAS instruction and no fences. The software‐only algorithms simulate the CAS instruction using a variation of Burns‐Lamport (1 fence) or Lamport's fast algorithm (3 fences). The algorithms are based on Attiya et al, where every thread in the critical section chooses its successor (if one is available). While Attiya et al use a binary tree for this purpose, it can also be done with a linear search. Surprisingly, all software‐only algorithms perform equally well under maximal contention on three different computer architectures; the hardware‐assisted versions perform better under minimal contention. The new algorithms are between −5% to 50% slower for maximal contention than the starvation‐free first‐come first‐served hardware‐assisted MCS algorithm, which uses two atomic instructions (fetch‐store and CAS); they are between 10% to 50% slower than MCS for minimal contention.
- 1 April 2018
- Published by Elsevier in Indagationes Mathematicae
- Vol. 29 (2) , 628-632
The quartet spaces of G. 't Hooft
- 1 April 2018
- Published by Elsevier in Indagationes Mathematicae
- Vol. 29 (2) , 628-632
The quartet spaces of G. 't Hooft