### Simple and efficient bounded concurrent timestamping and the traceable use abstractionSimple and efficient bounded concurrent timestamping and the traceable use abstraction

Access Restriction
Subscribed

 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

Source: ACM Digital Library