New combinatorial topology bounds for renaming: the lower bound
DOI10.1007/S00446-010-0108-2zbMATH Open1231.68068OpenAlexW2030003887MaRDI QIDQ992504FDOQ992504
Authors: Armando Castañeda, Sergio Rajsbaum 
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
Recommendations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distributed systems (68M14)
Cites Work
- Renaming in an asynchronous environment
- Title not available (Why is that?)
- More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
- The topological structure of asynchronous computability
- Title not available (Why is that?)
- Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
- Generalized FLP impossibility result for t-resilient asynchronous computations
- Subconsensus Tasks: Renaming Is Weaker Than Set Agreement
- Three-Processor Tasks Are Undecidable
- Algebraic spans
- Title not available (Why is that?)
- A simple algorithmically reasoned characterization of wait-free computation (extended abstract)
- Immediate atomic snapshots and fast renaming
- A topological treatment of early-deciding set-agreement
- 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
- Toward a Topological Characterization of Asynchronous Complexity
- Sharing memory robustly in message-passing systems
- The extended BG-simulation and the characterization of t-resiliency
- From adaptive renaming to set agreement
- A Note on the Homotopy Type of Wait-Free Atomic Snapshot Protocol Complexes
- Title not available (Why is that?)
- The asynchronous computability theorem for t-resilient tasks
- Simplicial maps from an orientable n-pseudomanifold into Sm with the octahedral triangulation
- Distributed Computing
- Title not available (Why is that?)
Cited In (20)
- The renaming problem in shared memory systems: an introduction
- A topological perspective on distributed network algorithms
- Combinatorial Topology of the Standard Chromatic Subdivision and Weak Symmetry Breaking for Six Processes
- Upper bound on the complexity of solving hard renaming
- Bounds on the Step and Namespace Complexity of Renaming
- Wait-freedom with advice
- Algebraic topology and distributed computing
- Structure theory of flip graphs with applications to weak symmetry breaking
- New combinatorial topology upper and lower bounds for renaming
- An Inductive-style Procedure for Counting Monochromatic Simplexes of Symmetric Subdivisions with Applications to Distributed Computing
- Linear space bootstrap communication schemes
- From wait-free to arbitrary concurrent solo executions in colorless distributed computing
- Renaming and the weakest family of failure detectors
- An equivariance theorem with applications to renaming
- The topology of local computing in networks
- Generalized symmetry breaking tasks and nondeterminism in concurrent objects
- An equivariance theorem with applications to renaming
- Why Extension-Based Proofs Fail
- A sharp threshold for the renameable-Horn and the \(q\)-Horn properties
- Tight Bounds for Asynchronous Renaming
This page was built for publication: New combinatorial topology bounds for renaming: the lower bound
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q992504)
