New combinatorial topology upper and lower bounds for renaming

DOI10.1145/1400751.1400791zbMath1301.68141OpenAlexW2008370075MaRDI QIDQ2934354

Sergio Rajsbaum, Armando Castañeda

Publication date: 12 December 2014

Published in: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1400751.1400791

zbMATH Keywords

distributed systemscombinatorial topologyrenamingshared memory systemswait-free computation

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14)

Related Items

An algorithmic approach to the asynchronous computability theorem ⋮ An Equivariance Theorem with Applications to Renaming ⋮ Structure theory of flip graphs with applications to weak symmetry breaking ⋮ A non-topological proof for the impossibility of \(k\)-set agreement ⋮ The solvability of consensus in iterated models extended with safe-consensus ⋮ Renaming and the weakest family of failure detectors ⋮ Combinatorial Topology of the Standard Chromatic Subdivision and Weak Symmetry Breaking for Six Processes ⋮ The renaming problem in shared memory systems: an introduction ⋮ Fully-adaptive algorithms for long-lived renaming ⋮ An Inductive-style Procedure for Counting Monochromatic Simplexes of Symmetric Subdivisions with Applications to Distributed Computing ⋮ New combinatorial topology bounds for renaming: the lower bound ⋮ Oblivious Collaboration