Document Open Access Logo

Schlegel Diagram and Optimizable Immediate Snapshot Protocol

Author Susumu Nishimura

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2017.22.pdf
  • Filesize: 0.66 MB
  • 16 pages

Document Identifiers

Author Details

Susumu Nishimura

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.OPODIS.2017.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.

Subject Classification

Keywords
  • Immediate snapshot protocol
  • Schlegel diagram
  • chromatic subdivision
  • program specialization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Hagit Attiya and Sergio Rajsbaum. The combinatorial structure of wait-free solvable tasks. SIAM J. Comput., 31(4):1286-1313, 2002. Google Scholar
  2. Fernando Benavides and Sergio Rajsbaum. The read/write protocol complex is collapsible. In LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, volume 9644 of LNCS, pages 179-191. Springer, 2016. Google Scholar
  3. Richard Bird. Pearls of Functional Algorithm Design. Cambridge University Press, 2010. Google Scholar
  4. Elizabeth Borowsky and Eli Gafni. Generalized FLP impossibility result for t-resilient asynchronous computations. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC, pages 91-100. ACM, 1993. Google Scholar
  5. Elizabeth Borowsky and Eli Gafni. Immediate atomic snapshots and fast renaming (extended abstract). In Proceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing, pages 41-51. ACM, 1993. Google Scholar
  6. Elizabeth Borowsky and Eli Gafni. A simple algorithmically reasoned characterization of wait-free computations. In Proc. of the 16th ACM Symposium on Principles of Distributed Computing, pages 189-198, 1997. Google Scholar
  7. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, 3rd edition, 2009. Google Scholar
  8. Eli Gafni, Yuan He, Petr Kuznetsov, and Thibault Rieutord. Read-write memory and k-set consensus as an affine task. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016), pages 6:1-6:17, 2016. Google Scholar
  9. Eli Gafni, Petr Kuznetsov, and Ciprian Manolescu. A generalized asynchronous computability theorem. In ACM Symposium on Principles of Distributed Computing, PODC '14, pages 222-231. ACM, 2014. Google Scholar
  10. Eli Gafni and Sergio Rajsbaum. Recursion in distributed computing. In Stabilization, Safety, and Security of Distributed Systems: 12th International Symposium, SSS 2010, volume 6366 of LNCS, pages 362-376. Springer, 2010. Google Scholar
  11. Maurice Herlihy, Dmitry N. Kozlov, and Sergio Rajsbaum. Distributed Computing Through Combinatorial Topology. Morgan Kaufmann, 2013. Google Scholar
  12. Maurice Herlihy and Sergio Rajsbaum. Set consensus using arbitrary objects (preliminary version). In Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, pages 324-333. ACM, 1994. Google Scholar
  13. Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. Journal of the ACM, 46(6):858-923, 1999. Google Scholar
  14. Gunnar Hoest and Nir Shavit. Toward a topological characterization of asynchronous complexity. SIAM J. Comput., 36(2):457-497, 2006. Google Scholar
  15. Neil D. Jones, Carsten K. Gomard, and Peter Sestoft. Partial evaluation and automatic program generation. Prentice Hall, 1993. Google Scholar
  16. Dmitry Kozlov. Combinatorial Algebraic Topology. Springer, 2008. Google Scholar
  17. Dmitry N. Kozlov. Chromatic subdivision of a simplicial complex. Homology, Homotopy and Applications, 14(2):197-209, 2012. Google Scholar
  18. Vikram Saraph, Maurice Herlihy, and Eli Gafni. Asynchronous computability theorems for t-resilient systems. In Distributed Computing - 30th International Symposium, DISC 2016, pages 428-441, 2016. Google Scholar
  19. Günter M. Ziegler. Lectures on Polytopes, volume 152 of Graduate Texts in Mathematics. Springer, 1995. Google Scholar
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