Bounds on the Step and Namespace Complexity of Renaming

DOI10.1137/16M1081439zbMath1410.68054OpenAlexW2908176613MaRDI QIDQ4646446

Armando Castañeda, Hagit Attiya, Ami Paz, Maurice P. Herlihy

Publication date: 14 January 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/16m1081439

zbMATH Keywords

distributed systemssymmetry breakingcombinatorial topologyrenamingshared memory systemswait-free computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed systems (68M14)

Related Items (2)

Synchronous \(t\)-resilient consensus in arbitrary graphs ⋮ A topological perspective on distributed network algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The renaming problem in shared memory systems: an introduction
• An equivariance theorem with applications to renaming
• All binomial identities are orderable
• New combinatorial topology bounds for renaming: the lower bound
• 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
• Algebraic spans
• Combinatorial Topology of the Standard Chromatic Subdivision and Weak Symmetry Breaking for Six Processes
• Counting-Based Impossibility Proofs for Renaming and Set Agreement
• Upper bound on the complexity of solving hard renaming
• A simple algorithmically reasoned characterization of wait-free computation (extended abstract)
• Immediate atomic snapshots and fast renaming
• New combinatorial topology bounds for renaming
• Weak symmetry breaking and abstract simplex paths
• Combinatorial algebraic topology

This page was built for publication: Bounds on the Step and Namespace Complexity of Renaming