RECORD
The Space Complexity of Long-lived and One-Shot Timestamp Implementations
Distributed, Parallel, and Cluster Computing · Submitted 29 Mar 2011
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We show that this bound is also asymptotically tight by providing a wait-free one-shot timestamp system that uses fewer than 2 sqrt{n} registers, thus establishing a space complexity gap between one-shot and long-lived timestamp systems.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
This paper is concerned with the problem of implementing an unbounded timestamp object from multi-writer atomic registers, in an asynchronous distributed system of n processors with distinct identifiers where timestamps are taken from an arbitrary universe. Ellen, Fatourou and Ruppert (2008) showed that sqrt{n}/2-O(1) registers are required for any obstruction-free implementation of long-lived timestamp systems from atomic registers (meaning processors can repeatedly get timestamps). We improve this existing lower bound in two ways. First we establish a lower bound of n/6 - O(1) registers for the obstruction-free long-lived timestamp problem. Previous such linear lower bounds were only known for constrained versions of the timestamp problem. This bound is asymptotically tight; Ellen, Fatourou and Ruppert (2008) constructed a wait-free algorithm that uses n-1 registers. Second we show that sqrt{n} - O(1) registers are required for any obstruction-free implementation of one-shot timestamp systems(meaning each processor can get a timestamp at most once). We show that this bound is also asymptotically tight by providing a wait-free one-shot timestamp system that uses fewer than 2 sqrt{n} registers, thus establishing a space complexity gap between one-shot and long-lived timestamp systems.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | This paper is concerned with the problem of implementing an unbounded timestamp object from multi-writer atomic registers, in an asynchronous distributed system of n processors with distinct identifiers where timestamps are taken from an arbitrary universe. | background 1.00 | 0.10 | 0.02 | asserted 0.80 |
| s1 | Ellen, Fatourou and Ruppert (2008) showed that sqrt{n}/2-O(1) registers are required for any obstruction-free implementation of long-lived timestamp systems from atomic registers (meaning processors can repeatedly get timestamps). | background 1.00 | 0.02 | 0.05 | asserted 1.00 |
| s2 | We improve this existing lower bound in two ways. | contribution 1.00 | 0.76 | 0.05 | asserted 0.89 |
| s3 | First we establish a lower bound of n/6 - O(1) registers for the obstruction-free long-lived timestamp problem. | result 0.88 | 0.96 | 0.41 | asserted 1.00 |
| s4 | Previous such linear lower bounds were only known for constrained versions of the timestamp problem. | gap 0.89 | 0.09 | 0.05 | asserted 1.00 |
| s5 | This bound is asymptotically tight; Ellen, Fatourou and Ruppert (2008) constructed a wait-free algorithm that uses n-1 registers. | interpretation 0.54 | 0.07 | 0.16 | asserted 1.00 |
| s6 | Second we show that sqrt{n} - O(1) registers are required for any obstruction-free implementation of one-shot timestamp systems(meaning each processor can get a timestamp at most once). | result 0.80 | 0.95 | 0.21 | asserted 1.00 |
| s7 | We show that this bound is also asymptotically tight by providing a wait-free one-shot timestamp system that uses fewer than 2 sqrt{n} registers, thus establishing a space complexity gap between one-shot and long-lived timestamp systems. | interpretation 0.43 | 0.95 | 0.53 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
This paper is concerned with the problem of implementing an unbounded timestamp object from multi-writer atomic registers, in an asynchronous distributed system of n processors with distinct identifiers where timestamps are taken from an arbitrary universe. Ellen, Fatourou and Ruppert (2008) showed that sqrt{n}/2-O(1) registers are required for any obstruction-free implementation of long-lived timestamp systems from atomic registers (meaning processors can repeatedly get timestamps). We improve this existing lower bound in two ways. First we establish a lower bound of n/6 - O(1) registers for the obstruction-free long-lived timestamp problem. Previous such linear lower bounds were only known for constrained versions of the timestamp problem. This bound is asymptotically tight; Ellen, Fatourou and Ruppert (2008) constructed a wait-free algorithm that uses n-1 registers. Second we show that sqrt{n} - O(1) registers are required for any obstruction-free implementation of one-shot timestamp systems(meaning each processor can get a timestamp at most once). We show that this bound is also asymptotically tight by providing a wait-free one-shot timestamp system that uses fewer than 2 sqrt{n} registers, thus establishing a space complexity gap between one-shot and long-lived timestamp systems.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.