Access Restriction

Author Dwork, Cynthia ♦ Waarts, Orli
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1999
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Distributed computing ♦ Distributed timestamps ♦ Fault-tolerant computing ♦ Shared memory ♦ Timestamping systems ♦ Traceable-use ♦ Wait-free algorithms
Abstract In a timestamping system, processors repeatedly choose timestamps so that the order of the timestamps obtained reflects the real-time order in which they were requested. Concurrent timestamping systems permit requests by multiple processors to be issued concurrently; in bounded timestamping systems the sizes of the timestamps and the size and number of shared variables are bounded. An algorithm is $\textit{wait-free}$ if there exists an a priori bound on the number of steps a processor must take in order to make progress, independent of the action or inaction of other processors. Letting $\textit{n}$ denote the number of procesors, we construct a simple wait-free bounded concurrent timestamping system requiring $\textit{O}(\textit{n})$ steps (accesses to shared memory) for a processor to read the current timestamps and determine the order among them, and $\textit{O}(\textit{n})$ steps to generate a timestamp, independent of the actions of the other processors. In addition, we introduce and implement the traceable use abstraction, a new primitive providing “inventory control” over values introduced by processors in the course of an algorithm execution. This abstraction has proved to be of great value in converting unbounded algorithms to bounded ones {Attiya and Rachman 1998; Dwork et al. 1992; 1993].
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1999-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 46
Issue Number 5
Page Count 34
Starting Page 633
Ending Page 666

Open content in new tab

   Open content in new tab
Source: ACM Digital Library