|
|||
|
IMADA - Department of Mathematics and Computer Science |
|
A desirable property of a distributed data structure is wait-freedom: when any process performs an operation on the data structure, it completes the operation in a finite number of of its own steps, regardless of how fast or slowly other processes execute. Unfortunately, wait-free data structures are usually complicated and expensive. An obstruction-free data structure provides a weaker progress guarantee: a process will complete its operation if it eventually executes enough steps without interference from other processes. Obstruction-free data structures are generally simpler and they are faster when there is no contention. We present a transformation that converts any obstruction-free algorithm for an asynchronous shared memory system into a wait-free algorithm when the system is semi-synchronous, even if the bound between the relative speed of processes is unknown. The overhead is negligible, unless an operation decides that it has run for too long without completing. This is joint work with Victor Luchangco, Mark Moir and Nir Shavit. Host: Joan Boyar SDU HOME | IMADA HOME | Previous Page Daniel Merkle |