The space complexity of unbounded timestamps

DOI10.1007/S00446-008-0060-6MaRDI QIDQ352241zbMATH OpenOpenAlexFDO

Authors Faith Ellen, Panagiota Fatourou, Eric Ruppert

Publication date 4 July 2013

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.925.4095

zbMATH Keywords

lower boundsshared memorytimestampsanonymousobstruction-freewait-free

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Network design and communication in computer systems (68M10) Distributed systems (68M14)

Recommendations

• The Space Complexity of Unbounded Timestamps
• Bounded Concurrent Time-Stamping
• Anonymous and fault-tolerant shared-memory computing

Cites work

• A new solution of Dijkstra's concurrent programming problem
• Algorithms adapting to point contention
• Anonymous and fault-tolerant shared-memory computing
• Bounded Concurrent Time-Stamping
• Bounded concurrent timestamp systems using vector clocks
• Bounded time-stamps
• Bounds on shared memory for mutual exclusion
• Computing on a partially eponymous ring
• Concerning the size of logical clocks in distributed systems
• Fast randomized consensus using shared memory
• How to share concurrent wait-free variables
• On the space complexity of randomized synchronization
• Randomized wait-free concurrent objects (extended abstract)
• Simple and efficient bounded concurrent timestamping and the traceable use abstraction
• The Space Complexity of Unbounded Timestamps
• Time and Space Lower Bounds for Nonblocking Implementations
• Time, clocks, and the ordering of events in a distributed system
• Time-Lapse Snapshots
• Time-space tradeoffs for implementations of snapshots

Cited in

(7)

• scientific article; zbMATH DE number 1825103 (Why is no real title available?)
• scientific article; zbMATH DE number 1979529 (Why is no real title available?)
• Efficient Bounded Timestamping from Standard Synchronization Primitives
• A tight space bound for consensus
• The Space Complexity of Unbounded Timestamps
• Linear space bootstrap communication schemes
• On the minimal information to encode timestamps in distributed computations.

This page was built for publication: The space complexity of unbounded timestamps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q352241)