Structure theory of flip graphs with applications to weak symmetry breaking (Q1659336)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Structure theory of flip graphs with applications to weak symmetry breaking |
scientific article |
Statements
Structure theory of flip graphs with applications to weak symmetry breaking (English)
0 references
15 August 2018
0 references
This paper is devoted to advancing the theoretical understanding of the iterated immediate snapshot (IIS) complexity of the Weak Symmetry Breaking task (WSB). The WSB for \(n\) processes is an inputless task with possible outputs \(0\) and \(1\). A distributed protocol is said to solve the WSB if in any execution without failed processes, there exists at least one process with has value \(0\) as well as at least one process which has value \(1\). WSB for \(n\) processes is equivalent to the Hard \((2n-2)\)-Renaming task, providing one of the main reasons to study its solvability and its complexity. The main theorem states that there exist infinitely many values of \(n\), such that WSB for \(n\) processes is solvable by a certain explicitly constructed \(3\)-round IIS protocol. In particular, the minimal number of rounds, which an IIS protocol needs in order to solve the WSB task, does not go to infinity, when the number of processes goes to infinity. The methods can also be used to generate such values of \(n\). The proofs are phrased in combinatorial language, the central notion is the notion of flip graph.
0 references
distributed computing
0 references
combinatorial algebraic topology
0 references
immediate snapshots
0 references
protocol complexes
0 references
weak symmetry breaking
0 references
chromatic subdivision
0 references
0 references
0 references