Bounds on the Costs of Multivalued Register Implementations

DOI10.1137/S0097539790190971MaRDI QIDQ4291561zbMATH OpenFDO

Authors Soma Chaudhuri, Jennifer L. Welch

Publication date 10 May 1994

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

registerstime and space complexityconcurrent computationconcurrent distributed systemshared memory registers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15)

Recommendations

• One-write algorithms for multivalued regular and atomic registers
• Almost optimal single reader, single writer atomic register
• Converting Lamport's regular register to atomic register
• Step-optimal implementations of large single-writer registers
• Step optimal implementations of large single-writer registers

Cited in

(13)

• Weak atomicity: A helpful notion in the construction of atomic shared variables
• scientific article; zbMATH DE number 1693496 (Why is no real title available?)
• Algorithms – ESA 2004
• Progress-space tradeoffs in single-writer memory implementations
• Information-theoretic lower bounds on the storage cost of shared memory emulation
• scientific article; zbMATH DE number 2013826 (Why is no real title available?)
• Step optimal implementations of large single-writer registers
• Space Complexity of Fault-Tolerant Register Emulations
• Hundreds of impossibility results for distributed computing
• How Fast Reads Affect Multi-Valued Register Simulations
• One-write algorithms for multivalued regular and atomic registers
• How a rainbow coloring function can simulate wait-free handshaking
• Step-optimal implementations of large single-writer registers

This page was built for publication: Bounds on the Costs of Multivalued Register Implementations

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