Simple and efficient bounded concurrent timestamping and the traceable use abstraction

Abstract

In a limestamping 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 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 denote the number of processors, we construct a simple wait-free bounded concurrent timestamping system requiring O(n) steps (accesses to shared memory) for a processor to read the current timestamps and determine the order among them, and O(n) steps to generate a timestamp, independent of the actions of 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]. © 1999 ACM.