Structure theory of flip graphs with applications to weak symmetry breaking (Q1659336)

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.