Combinatorial Topology of the Standard Chromatic Subdivision and Weak Symmetry Breaking for Six Processes

DOI10.1007/978-3-319-31580-5_7MaRDI QIDQ4608477zbMATH OpenOpenAlexFDO

Authors Dmitry N. Kozlov

Publication date 20 March 2018

Published in Springer INdAM Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.03944

zbMATH Keywords

protocol complexesstandard chromatic subdivisionweak symmetry breaking

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) PL-topology (57Q99)

Abstract: In this paper we study a family of discrete configuration spaces, the so-called protocol complexes, which are of utmost importance in theoretical distributed computing. Specifically, we consider questions of the existance of compliant binary labelings on the vertices of iterated standard chromatic subdivisions of an n-simplex. The existance of such labelings is equivalent to the existance of distributed protocols solving Weak Symmetry Breaking task in the standard computational model. As a part of our formal model, we introduce function sb(n), defined for natural numbers n, called the symmetry breaking function. From the geometric point of view sb(n) denotes the minimal number of iterations of the standard chromatic subdivision of an (n-1)-simplex, which is needed for the compliant binary labeling to exist. From the point of distributed computing, the function sb(n) measures the minimal number of rounds in a protocol solving the Weak Symmetry Breaking task. In addition to the development of combinatorial topology, which is applicable in a broader context, our main contribution is the proof of new bounds for the function sb(n). Accordingly, the bulk of the paper is taken up by in-depth analysis of the structure of adjacency graph on the set of n-simplices in iterated standard chromatic subdivision of an n-simplex. On the algorithmic side, we provide the first distributed protocol solving Weak Symmetry Breaking task in the layered immediate snapshot computational model for some number of processes. It is well known, that the smallest number of processes for which Weak Symmetry Breaking task is solvable is 6. Based on our analysis, we are able to find a very fast explicit protocol, solving the Weak Symmetry Breaking for 6 processes using only 3 rounds. Furthermore, we show that no protocol can solve Weak Symmetry Breaking in fewer than 2 rounds.

Recommendations

• Chromatic properties of 6-regular graphs embedded on the Klein bottle
• scientific article; zbMATH DE number 5823677
• Topological lower bounds for the chromatic number: a hierarchy
• On topological relaxations of chromatic conjectures
• On the strength of chromatic symmetric homology for graphs
• Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
• Simplicial subdivisions and the chromatic number of a group
• Chromatic subdivision of a simplicial complex
• A generalization of chromatic polynomial of a graph subdivision
• On chromatic symmetric homology and planarity of graphs

Cites work

• scientific article; zbMATH DE number 1179121 (Why is no real title available?)
• scientific article; zbMATH DE number 6991613 (Why is no real title available?)
• All binomial identities are orderable
• Chromatic subdivision of a simplicial complex
• Combinatorial algebraic topology
• Counting-based impossibility proofs for renaming and set agreement
• Distributed computing through combinatorial topology
• Impossibility results for distributed computing
• New combinatorial topology bounds for renaming: the lower bound
• New combinatorial topology bounds for renaming: the upper bound
• New combinatorial topology upper and lower bounds for renaming
• Structure theory of flip graphs with applications to weak symmetry breaking
• The topological structure of asynchronous computability
• Topology of the immediate snapshot complexes
• Topology of the view complex
• Upper bound on the complexity of solving hard renaming
• Weak symmetry breaking and abstract simplex paths

Cited in

(7)

• scientific article; zbMATH DE number 6991613 (Why is no real title available?)
• Structure theory of flip graphs with applications to weak symmetry breaking
• The time complexity of consensus under oblivious message adversaries
• Bounds on the step and namespace complexity of renaming
• All binomial identities are orderable
• An inductive-style procedure for counting monochromatic simplexes of symmetric subdivisions with applications to distributed computing
• Iterated chromatic subdivisions are collapsible

This page was built for publication: Combinatorial Topology of the Standard Chromatic Subdivision and Weak Symmetry Breaking for Six Processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608477)