Simple and efficient bounded concurrent timestamping or bounded concurrent timestamp systems are comprehensible!

Abstract

In a timestamping system processors repeatedly choose labels in such a way that the order of the labels assigned 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 labels and the amount of auxiliary storage are bounded. Letting n denote the number of processors, we construct a simple bounded concurrent timestamping system requiring O(n) steps (accesses to shared memory) to read the current labels and determine the order among them, and O(n) steps to generate a label. In addition, we introduce the Traceable Use abstraction, which, roughly speaking, permits a processor to know and to control which of its own values are currently in use in the system.