New combinatorial topology bounds for renaming: the lower bound

DOI10.1007/s00446-010-0108-2zbMath1231.68068OpenAlexW2030003887MaRDI QIDQ992504

Sergio Rajsbaum, Armando Castañeda

Publication date: 9 September 2010

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-010-0108-2

zbMATH Keywords

lower boundcombinatorial topologyrenamingshared-memory

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14)

Related Items (14)

Tight Bounds for Asynchronous Renaming ⋮ Structure theory of flip graphs with applications to weak symmetry breaking ⋮ From wait-free to arbitrary concurrent solo executions in colorless distributed computing ⋮ Renaming and the weakest family of failure detectors ⋮ Why Extension-Based Proofs Fail ⋮ Combinatorial Topology of the Standard Chromatic Subdivision and Weak Symmetry Breaking for Six Processes ⋮ The renaming problem in shared memory systems: an introduction ⋮ Linear space bootstrap communication schemes ⋮ An equivariance theorem with applications to renaming ⋮ 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 ⋮ Generalized Symmetry Breaking Tasks and Nondeterminism in Concurrent Objects ⋮ Wait-freedom with advice ⋮ A topological perspective on distributed network algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A topological treatment of early-deciding set-agreement
• From adaptive renaming to set agreement
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• A classification of wait-free loop agreement tasks
• New combinatorial topology upper and lower bounds for renaming
• The Combinatorial Structure of Wait-Free Solvable Tasks
• The topological structure of asynchronous computability
• Toward a Topological Characterization of Asynchronous Complexity
• Renaming in an asynchronous environment
• Subconsensus Tasks: Renaming Is Weaker Than Set Agreement
• Three-Processor Tasks Are Undecidable
• Sharing memory robustly in message-passing systems
• Algebraic spans
• A Note on the Homotopy Type of Wait-Free Atomic Snapshot Protocol Complexes
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• The extended BG-simulation and the characterization of t-resiliency
• Generalized FLP impossibility result for t-resilient asynchronous computations
• The asynchronous computability theorem for t-resilient tasks
• A simple algorithmically reasoned characterization of wait-free computation (extended abstract)
• Immediate atomic snapshots and fast renaming
• Distributed Computing
• Simplicial maps from an orientable n-pseudomanifold into Sm with the octahedral triangulation

This page was built for publication: New combinatorial topology bounds for renaming: the lower bound