The problem of bounded concurrent timestamping systems (CTSS) is developing an algorithmic and bounded data storage support for a system in which processors repeatedly choose labels whose order reflects the real-time order in which the labels have been selected. The operations concerned are scan, to read the current labels and determine their order, and label, to generate a label. The basic technique of first obtaining an unbounded CTSS and then finding a way of recycling the labels is inherited from previous work.

This paper provides an important advance in CTSS. It contains two major results. One, of a comparative character, is that the proposed bounded CTSS requires O ( n ) steps (accesses to shared memory) for both scan and label.

The other result, which is more methodological and of greater importance, is that the authors have departed from a standard approach to the unbounded case, which was based on a shared joint pool of labels and a recursively defined precedence graph. Avoiding the precedence graph, the paper draws on the idea of each processor having a local pool of values and a label being a vector of values, one for each processor. Quite naturally, this solution leads to the worsening of the other characteristic bound, the size of registers, from O ( n ) to O ( n log n ) .

The proposed method uses an interesting concept, called the traceable use abstraction, which has reportedly yielded positive results in other contexts aimed at boundedness. This mechanism allows the processor to track which of its own values are currently being used in the system. The scan and label operations are implemented through more basic constructs, consume, update, and garbage collection. A set of semantic restrictions, called continuity, limited indirection, and limited mobility, imposed on the implementation help ensure that the basic primitive RWRWR (R stands for “read” and W for “write” operations on a single-writer-multi-reader shared register) satisfies the following correctness properties of the CTSS: regularity, monotonicity, detectability, and boundedness.

The paper’s style is good: it begins with a clear outline of the key idea and sharply delineates the previous work. The reader might encounter minor difficulties caused by a certain amount of juggling of the subscripts and indices (such as the transposition of b, c, and k in Sections 4.3 and 4.4). I also found the usage of “owner,” “belongs to,” and “producer” confusing: the authors distinguish the first two terms, while the second and third are defined identically. Some proofs of lemmas involving proving and using the definition of regularity are not totally clear, involving a lot of supposedly equivalent “linguistic transformations” (done behind the scenes) of statements built from words like “before,” “after,” “terminates,” and “begins.”