A complexity separation between the cache-coherent and distributed shared memory models

DOI10.1145/1993806.1993822MaRDI QIDQ2943389zbMATH OpenOpenAlexFDO

Authors Wojciech Golab

Publication date 11 September 2015

Published in Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.5153, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.718.5928

zbMATH Keywords

shared memory models

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed systems (68M14)

Abstract: We consider asynchronous multiprocessor systems where processes communicate by accessing shared memory. Exchange of information among processes in such a multiprocessor necessitates costly memory accesses called emph{remote memory references} (RMRs), which generate communication on the interconnect joining processors and main memory. In this paper we compare two popular shared memory architecture models, namely the emph{cache-coherent} (CC) and emph{distributed shared memory} (DSM) models, in terms of their power for solving synchronization problems efficiently with respect to RMRs. The particular problem we consider entails one process sending a "signal" to a subset of other processes. We show that a variant of this problem can be solved very efficiently with respect to RMRs in the CC model, but not so in the DSM model, even when we consider amortized RMR complexity. To our knowledge, this is the first separation in terms of amortized RMR complexity between the CC and DSM models. It is also the first separation in terms of RMR complexity (for asynchronous systems) that does not rely in any way on wait-freedom---the requirement that a process makes progress in a bounded number of its own steps.

Recommendations

• A tight RMR lower bound for randomized mutual exclusion
• An \(O(1)\) RMRs leader election algorithm
• Brief announcement, a tight RMR lower bound for randomized mutual exclusion
• scientific article; zbMATH DE number 1760040
• Randomized mutual exclusion with sub-logarithmic RMR-complexity

Cites work

• scientific article; zbMATH DE number 795590 (Why is no real title available?)
• Almost-Everywhere Secure Computation
• Broadcasting in dynamic radio networks
• Consensus algorithms with one-bit messages
• Continuous consensus via common knowledge
• Distributed computation in dynamic networks
• Fault Tolerance in Networks of Bounded Degree
• Flooding time in edge-Markovian dynamic graphs
• Gradient clock synchronization in dynamic networks
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• Knowledge and common knowledge in a distributed environment
• Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony
• Optimal gradient clock synchronization in dynamic networks
• Parsimonious flooding in dynamic graphs
• Perfectly secure message transmission
• Programming simultaneous actions using common knowledge
• Reaching Agreement in the Presence of Faults

Cited in

(6)

• An \(O(1)\) RMRs leader election algorithm
• scientific article; zbMATH DE number 1760040 (Why is no real title available?)
• A time complexity lower bound for adaptive mutual exclusion
• An \(O(1)\) RMRs leader election algorithm
• RMR-efficient implementations of comparison primitives using read and write operations
• Remote memory references at block granularity

This page was built for publication: A complexity separation between the cache-coherent and distributed shared memory models

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