Algorithms adapting to point contention
Authors:
Open Access
- 1 July 2003
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 50 (4) , 444-468
Abstract
This article introduces the sieve , a novel building block that allows to adapt to the number of simultaneously active processes (the point contention ) during the execution of an operation. We present an implementation of the sieve in which each sieve operation requires O ( k log k ) steps, where k is the point contention during the operation.The sieve is the cornerstone of the first wait-free algorithms that adapt to point contention using only read and write operations. Specifically, we present efficient algorithms for long-lived renaming, timestamping and collecting information.Keywords
This publication has 11 references indexed in Scilit:
- Adaptive and efficient mutual exclusionDistributed Computing, 2002
- An adaptive collect algorithm with applicationsDistributed Computing, 2002
- Long lived adaptive splitter and applicationsDistributed Computing, 2002
- The BG distributed simulation algorithmDistributed Computing, 2001
- Adaptive and Efficient Algorithms for Lattice Agreement and RenamingSIAM Journal on Computing, 2001
- Adaptive solutions to the mutual exclusion problemDistributed Computing, 1994
- Multi-writer composite registersDistributed Computing, 1994
- Atomic snapshots of shared memoryJournal of the ACM, 1993
- Wait-free synchronizationACM Transactions on Programming Languages and Systems, 1991
- Renaming in an asynchronous environmentJournal of the ACM, 1990