Magic functions
Cynthia Dwork, Moni Naor, et al.
Journal of the ACM
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.
Cynthia Dwork, Moni Naor, et al.
Journal of the ACM
Miklos Ajtai, James Aspnes, et al.
Journal of Algorithms
Cynthia Dwork, Nancy Lynch, et al.
Journal of the ACM
Uriel Feige, László Lovász
STOC 1992