Downloads: 34

Files in This Item:
File Description SizeFormat 
LIPIcs.OPODIS.2017.22.pdf686.06 kBAdobe PDFView/Open
Title: Schlegel Diagram and Optimizable Immediate Snapshot Protocol
Authors: NISHIMURA, Susumu  kyouindb  KAKEN_id
Author's alias: 西村, 進
Keywords: Immediate snapshot protocol
Schlegel diagram
chromatic subdivision
program specialization
Issue Date: 2018
Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Journal title: Leibniz International Proceedings in Informatics (LIPIcs)
Volume: 95
Thesis number: 22
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.
Description: 21st International Conference on Principles of Distributed Systems (OPODIS 2017), 18-20 December 2017, Lisbon, Portugal.
Rights: © Susumu Nishimura; licensed under Creative Commons License CC-BY 21st International Conference on Principles of Distributed Systems (OPODIS 2017).
URI: http://hdl.handle.net/2433/231324
DOI(Published Version): 10.4230/LIPIcs.OPODIS.2017.22
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.