Simple and efficient bounded concurrent timestamping and the traceable use abstraction

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 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 n denote the number of procesors, 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 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].