Search Results

Documents authored by Nishimura, Susumu

Document
DOI: 10.4230/LIPIcs.OPODIS.2017.22
Schlegel Diagram and Optimizable Immediate Snapshot Protocol

Authors: Susumu Nishimura

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
In the topological study of distributed systems, the immediate snapshot is the fundamental computation block for the topological characterization of wait-free solvable tasks. However, in reality, the immediate snapshot is not available as a native built-in operation on shared memory distributed systems. Borowsky and Gafni have proposed a wait-free multi-round protocol that implements the immediate snapshot using more primitive operations, namely the atomic reads and writes. In this paper, up to an appropriate reformulation on the original protocol by Borowsky and Gafni, we establish a tight link between each round of the protocol and a topological operation of subdivision using Schlegel diagram. Due to the fact shown by Kozlov that the standard chromatic subdivision is obtained by iterated subdivision using Schlegel diagram, the reformulated version is proven to compute the immediate snapshot in a topologically smoother way. We also show that the reformulated protocol is amenable to optimization: Since each round restricts the possible candidates of output to an iteratively smaller region of finer subdivision, each process executing the protocol can decide at an earlier round, beyond which the same final output is reached no matter how the remaining rounds are executed. This reduces the number of read and write operations involved in the overall execution of the protocol, relieving the bottleneck of access to shared memory.
Cite as

Susumu Nishimura. Schlegel Diagram and Optimizable Immediate Snapshot Protocol. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{nishimura:LIPIcs.OPODIS.2017.22,
  author =	{Nishimura, Susumu},
  title =	{{Schlegel Diagram and Optimizable Immediate Snapshot Protocol}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.22},
  URN =		{urn:nbn:de:0030-drops-86464},
  doi =		{10.4230/LIPIcs.OPODIS.2017.22},
  annote =	{Keywords: Immediate snapshot protocol, Schlegel diagram, chromatic subdivision, program specialization}
}
Document
DOI: 10.4230/LIPIcs.CSL.2013.578
A Fully Abstract Game Semantics for Parallelism with Non-Blocking Synchronization on Shared Variables

Authors: Susumu Nishimura

Published in: LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013)

Abstract
We present a fully abstract game semantics for an Algol-like parallel language with non-blocking synchronization primitive. Elaborating on Harmer's game model for nondeterminism, we develop a game framework appropriate for modeling parallelism. The game is a sophistication of the wait-notify game proposed in a previous work, which makes the signals for thread scheduling explicit with a certain set of extra moves. The extra moves induce a Kleisli category of games, on which we develop a game semantics of the Algol-like parallel language and establish the full abstraction result with a significant use of the non-blocking synchronization operation.
Cite as

Susumu Nishimura. A Fully Abstract Game Semantics for Parallelism with Non-Blocking Synchronization on Shared Variables. In Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 23, pp. 578-596, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{nishimura:LIPIcs.CSL.2013.578,
  author =	{Nishimura, Susumu},
  title =	{{A Fully Abstract Game Semantics for Parallelism with Non-Blocking Synchronization on Shared Variables}},
  booktitle =	{Computer Science Logic 2013 (CSL 2013)},
  pages =	{578--596},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-60-6},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{23},
  editor =	{Ronchi Della Rocca, Simona},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.578},
  URN =		{urn:nbn:de:0030-drops-42201},
  doi =		{10.4230/LIPIcs.CSL.2013.578},
  annote =	{Keywords: shared variable parallelism, non-blocking synchronization, full abstraction, game semantics}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact