TY - GEN

T1 - The notion of a timed register and its application to indulgent synchronization

AU - Raynal, Michel

AU - Taubenfeld, Gadi

PY - 2007

Y1 - 2007

N2 - A new type of shared object, called timed register, is proposed and used to design indulgent timing-based algorithms. A timed register generalizes the notion of an atomic register as follows: if a process invokes two consecutive operations on the same timed register which are a read followed by a write, then the write operation is executed only if it is invoked at most d time units after the read operation, where d is defined as part of the read operation. In this context, a timing-based algorithm is an algorithm whose correctness relies on the existence of a bound Δ such that any pair of consecutive constrained read and write operations issued by the same process on the same timed register are separated by at most Δ time units. An indulgent algorithm is an algorithm that always guarantees the safety properties, and ensures the liveness property as soon as the timing assumptions are satisfied. The usefulness of this new type of shared object is demonstrated by presenting simple and elegant indulgent timing-based algorithms that solve the mutual exclusion, l-exclusion, adaptive renaming,test&set, and consensus problems. Interestingly, timed registers are universal objects in systems with process crashes and transient timing failures (i.e., they allow building any concurrent object with a sequential specification). The paper also suggests connections with schedulers and contention managers.

AB - A new type of shared object, called timed register, is proposed and used to design indulgent timing-based algorithms. A timed register generalizes the notion of an atomic register as follows: if a process invokes two consecutive operations on the same timed register which are a read followed by a write, then the write operation is executed only if it is invoked at most d time units after the read operation, where d is defined as part of the read operation. In this context, a timing-based algorithm is an algorithm whose correctness relies on the existence of a bound Δ such that any pair of consecutive constrained read and write operations issued by the same process on the same timed register are separated by at most Δ time units. An indulgent algorithm is an algorithm that always guarantees the safety properties, and ensures the liveness property as soon as the timing assumptions are satisfied. The usefulness of this new type of shared object is demonstrated by presenting simple and elegant indulgent timing-based algorithms that solve the mutual exclusion, l-exclusion, adaptive renaming,test&set, and consensus problems. Interestingly, timed registers are universal objects in systems with process crashes and transient timing failures (i.e., they allow building any concurrent object with a sequential specification). The paper also suggests connections with schedulers and contention managers.

KW - Asynchronous shared memory system

KW - Atomic register

KW - Concurrent object

KW - Consensus

KW - Contention manager

KW - Mutual exclusion

KW - Process crash

KW - Renaming

KW - Simplicity

KW - Test&set

KW - Timing assumption

KW - Timing constraint

KW - Universal object

KW - Wait-free implementation

UR - http://www.scopus.com/inward/record.url?scp=35248889914&partnerID=8YFLogxK

U2 - 10.1145/1248377.1248413

DO - 10.1145/1248377.1248413

M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???

AN - SCOPUS:35248889914

SN - 159593667X

SN - 9781595936677

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 200

EP - 209

BT - SPAA'07

T2 - SPAA'07: 19th Annual Symposium on Parallelism in Algorithms and Architectures

Y2 - 9 June 2007 through 11 June 2007

ER -