New combinatorial topology upper and lower bounds for renaming
From MaRDI portal
Publication:2934354
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
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
