Bounds on the step and namespace complexity of renaming

DOI10.1137/16M1081439MaRDI QIDQ4646446zbMATH OpenOpenAlexFDO

Authors Hagit Attiya, Armando Castañeda, Ami Paz, Maurice 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

combinatorial topologydistributed systemsrenamingshared memory systemssymmetry breakingwait-free computation

Mathematics Subject Classification ID

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

Recommendations

• Upper bound on the complexity of solving hard renaming
• New combinatorial topology bounds for renaming: the upper bound
• New combinatorial topology bounds for renaming: the lower bound
• New combinatorial topology upper and lower bounds for renaming
• The renaming problem: recent developments and open questions

Cites work

• A simple algorithmically reasoned characterization of wait-free computation (extended abstract)
• Algebraic spans
• All binomial identities are orderable
• An equivariance theorem with applications to renaming
• Combinatorial algebraic topology
• Combinatorial Topology of the Standard Chromatic Subdivision and Weak Symmetry Breaking for Six Processes
• Counting-based impossibility proofs for renaming and set agreement
• Distributed computing through combinatorial topology
• scientific article; zbMATH DE number 4102053 (Why is no real title available?)
• Immediate atomic snapshots and fast renaming
• New combinatorial topology bounds for renaming: the lower bound
• New combinatorial topology bounds for renaming: the upper bound
• Renaming in an asynchronous environment
• Subconsensus Tasks: Renaming Is Weaker Than Set Agreement
• The Combinatorial Structure of Wait-Free Solvable Tasks
• The renaming problem in shared memory systems: an introduction
• The renaming problem: recent developments and open questions
• The topological structure of asynchronous computability
• Toward a Topological Characterization of Asynchronous Complexity
• Upper bound on the complexity of solving hard renaming
• Weak symmetry breaking and abstract simplex paths

Cited in

(8)

• Upper bound on the complexity of solving hard renaming
• A topological perspective on distributed network algorithms
• Synchronous \(t\)-resilient consensus in arbitrary graphs
• Synchronous t-resilient consensus in arbitrary graphs
• The time complexity of consensus under oblivious message adversaries
• The topology of local computing in networks
• The topology of local computing in networks
• A speedup theorem for asynchronous computation with applications to consensus and approximate agreement

This page was built for publication: Bounds on the step and namespace complexity of renaming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4646446)