Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-09T13:36:08.815Z Has data issue: false hasContentIssue false
  • English
  • Français

Weak symmetry breaking and abstract simplex paths

Published online by Cambridge University Press:  16 February 2015

DMITRY N. KOZLOV
DMITRY N. KOZLOV*
Affiliation:
Department of Mathematics, University of Bremen, 28334 Bremen, Federal Republic of Germany Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Motivated by questions in theoretical distributed computing, we develop the combinatorial theory of abstract simplex path subdivisions. Our main application is a short and structural proof of a theorem of Castañeda and Rajsbaum. This theorem in turn implies the solvability of the weak symmetry breaking task in the immediate snapshot wait-free model in the case when the number of processes is not a power of a prime number.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 25 , Issue 6 , September 2015 , pp. 1432 - 1462
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Attiya, H., Bar-Noy, A., Dolev, D., Peleg, D. and Reischuck, R. (1990) Renaming in an asynchronous environment. Journal of the ACM 37 (3) 524–548.Google Scholar
Attiya, H., Castañeda, A., Herlihy, M. and Paz, A. (2013) Upper bound on the complexity of solving hard renaming. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC) 190–199.Google Scholar
Attiya, H. and Paz, A. (2012) Counting-based impossibility proofs for renaming and set agreement. In: 26th International Symposium on DIStributed Computing, Salvador, Brazil. Lecture Notes in Computer Science 7611 356–370.CrossRefGoogle Scholar
Attiya, H. and Welch, J. (2004) Distributed computing: Fundamentals, simulations and advanced topics. Wiley Series on Parallel and Distributed Computing, 2nd edition, Wiley-Interscience 432.Google Scholar
Castañeda, A. and Rajsbaum, S. (2008) New combinatorial topology upper and lower bounds for renaming. In: Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing, ACM, New York 295–304.Google Scholar
Castañeda, A. and Rajsbaum, S. (2010) New combinatorial topology bounds for renaming: The lower bound. Distributed Computing 25 (5) 287–301.Google Scholar
Castañeda, A. and Rajsbaum, S. (2012a) New combinatorial topology bounds for renaming: the upper bound. Journal of the ACM 59 (1) (Article No. 3).Google Scholar
Castañeda, A. and Rajsbaum, S. (2012b) An inductive-style procedure for counting monochromatic simplexes of symmetric subdivisions with applications to distributed computing. Electronic Notes in Theoretical Computer Science 283 13–27.Google Scholar
Coxeter, H. S. M. (1973) Regular Polytopes. 3rd edition, Dover Publications Inc., New York xiv+321.Google Scholar
Gafni, E., Herlihy, M. and Rajsbaum, S. (2006) Subconsensus tasks: Renaming is weaker than set agreement. In: Proceedings of the 20th International Symposium on Distributed Computing, Springer, New York 329–338.Google Scholar
Grünbaum, B. (2003) Convex Polytopes, 2nd edition, Graduate Texts in Mathematics, volume 221, Springer-Verlag, New York xvi+468.Google Scholar
Herlihy, M. (1991) Wait-free synchronization. ACM Transactions on Programming Languages and Systems (TOPLAS) 13 (1) 124–149.CrossRefGoogle Scholar
Herlihy, M., Kozlov, D. N. and Rajsbaum, S. (2014) Distributed Computing through Combinatorial Topology, Elsevier 336.Google Scholar
Herlihy, M. and Shavit, N. (1999) The topological structure of asynchronous computability. Journal of the ACM 46 (6) 858–923.CrossRefGoogle Scholar
Imbs, D., Rajsbaum, S. and Raynal, M. (2011) The universe of symmetry breaking tasks, structural information and communication complexity. Lecture Notes in Computer Science 6796 66–77.Google Scholar
Kozlov, D. N. (2008) Combinatorial Algebraic Topology, Algorithms and Computation in Mathematics, volume 21, Springer-Verlag Berlin Heidelberg, XX, 390 p. 115 illus.CrossRefGoogle Scholar
Kozlov, D. N. (2012) Chromatic Subdivision of a Simplicial Complex. Homology, Homotopy and Applications 14 (2) 197–209.Google Scholar
Kozlov, D. N. (2013) Topology of the view complex. arXiv:1311.7283 [cs.DC].Google Scholar