English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

This article is concerned with the problem of implementing an unbounded timestamp object from multiwriter atomic registers, in an asynchronous distributed system of n processes with distinct identifiers where timestamps are taken from an arbitrary universe. Ellen et al. [2008] showed that √n/2 − O(1) registers are required for any obstruction-free implementation of long-lived timestamp systems from atomic registers (meaning processes can repeatedly get timestamps). We improve this existing lower bound in two ways. First we establish a lower bound of n/6 − 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 et al. [2008] constructed a wait-free algorithm that uses n − 1 registers. Second we show that √2n − log n − O(1) registers are required for any obstruction-free implementation of one-shot timestamp systems (meaning each process 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 at most ⌈2√n⌉ registers, thus establishing a space complexity gap between one-shot and long-lived timestamp systems.

The Space Complexity of Long-Lived and One-Shot Timestamp Implementations