License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2017.22
URN: urn:nbn:de:0030-drops-86464
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8646/
Go to the corresponding LIPIcs Volume Portal

Nishimura, Susumu

Schlegel Diagram and Optimizable Immediate Snapshot Protocol

pdf-format:
LIPIcs-OPODIS-2017-22.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{nishimura:LIPIcs:2018:8646,
  author =	{Susumu Nishimura},
  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 =	{James Aspnes and Alysson Bessani and Pascal Felber and Jo{\~a}o Leit{\~a}o},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8646},
  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}
}

Keywords: Immediate snapshot protocol, Schlegel diagram, chromatic subdivision, program specialization
Collection: 21st International Conference on Principles of Distributed Systems (OPODIS 2017)
Issue Date: 2018
Date of publication: 28.03.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI