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

DOI10.1007/978-3-319-31580-5_7zbMATH Open1426.68185arXiv1506.03944OpenAlexW1894549304MaRDI QIDQ4608477FDOQ4608477

Authors: Dmitry N. Kozlov 

Publication date: 20 March 2018

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

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.

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

Recommendations

• Chromatic properties of 6-regular graphs embedded on the Klein bottle
• scientific article
• 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

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)

Cites Work

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

Cited In (7)

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

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)