Weak symmetry breaking and abstract simplex paths
arXiv:1311.7289 · doi:10.1017/S0960129514000085
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 the theorem of Castaneda 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.
revised version, 30 pages To appear in Mathematical Structures in Computer Science