The topological structure of asynchronous computability

DOI10.1145/331524.331529zbMath1161.68469OpenAlexW2149907923WikidataQ56386812 ScholiaQ56386812MaRDI QIDQ3158560

Publication date: 25 January 2005

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/331524.331529

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Distributed systems (68M14) PL-topology (57Q99)

Related Items

Tasks in modular proofs of concurrent algorithms, The solvability of consensus in iterated models extended with safe-consensus, Impure Simplicial Complexes: Complete Axiomatization, Optimal algorithms for synchronous Byzantine \(k\)-set agreement, Reaching agreement in the presence of contention-related crash failures, Why Extension-Based Proofs Fail, Optimal algorithms for synchronous Byzantine \(k\)-set agreement, On the Validity of Consensus, Wait-free solvability of colorless tasks in anonymous shared-memory model, Wait-free approximate agreement on graphs, A distributed computing perspective of unconditionally secure information transmission in Russian cards problems, Collapsibility of read/write models using discrete Morse theory, An algorithmic approach to the asynchronous computability theorem, An Equivariance Theorem with Applications to Renaming, Unnamed Item, The \(k\)-simultaneous consensus problem, On the computability power and the robustness of set agreement-oriented failure detector classes, Shared-object system equilibria: delay and throughput analysis, Unnamed Item, Wanted dead or alive: epistemic logic for impure simplicial complexes, A Separation of n-consensus and (n + 1)-consensus Based on Process Scheduling, The Computability of Relaxed Data Structures: Queues and Stacks as Examples, Distributed universality, Beyond Lamport's Happened-before, Tight Bounds for Asynchronous Renaming, Geometric and combinatorial views on asynchronous computability, Structure theory of flip graphs with applications to weak symmetry breaking, From wait-free to arbitrary concurrent solo executions in colorless distributed computing, The topology of distributed adversaries, Schlegel Diagram and Optimizable Immediate Snapshot Protocol, Distributed computability: relating \(k\)-immediate snapshot and \(x\)-set agreement, A non-topological proof for the impossibility of \(k\)-set agreement, Power and limits of distributed computing shared memory models, Agreeing within a few writes, On the uncontended complexity of anonymous agreement, Communication Complexity of Wait-Free Computability in Dynamic Networks, Randomized \(k\)-set agreement in crash-prone and Byzantine asynchronous systems, Iterated chromatic subdivisions are collapsible, Life beyond set agreement, Partial synchrony based on set timeliness, Renaming and the weakest family of failure detectors, Gathering identical autonomous systems on a circle using stigmergy, The Iterated Restricted Immediate Snapshot Model, Of choices, failures and asynchrony: the many faces of set agreement, Combinatorial Topology of the Standard Chromatic Subdivision and Weak Symmetry Breaking for Six Processes, Tight bounds for \(k\)-set agreement with limited-scope failure detectors, Anonymous and fault-tolerant shared-memory computing, Common2 extended to stacks and unbounded concurrency, Renaming in synchronous message passing systems with Byzantine failures, Locality and checkability in wait-free computing, Waiting in concurrent algorithms, The renaming problem in shared memory systems: an introduction, The Weakest Failure Detector for Message Passing Set-Agreement, Topology of the immediate snapshot complexes, A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma, Randomized two-process wait-free test-and-set, Hundreds of impossibility results for distributed computing, A simple characterization of asynchronous computations, Linear space bootstrap communication schemes, Threshold protocols in survivor set systems, The disagreement power of an adversary, On set consensus numbers, The minimum information about failures for solving non-local tasks in message-passing systems, An equivariance theorem with applications to renaming, A Sound Foundation for the Topological Approach to Task Solvability, A closer look at fault tolerance, GPU schedulers: how fair is fair enough?, Anonymous obstruction-free \((n,k)\)-set agreement with \(n-k+1\) atomic read/write registers, Bounds on the Step and Namespace Complexity of Renaming, The computability of relaxed data structures: queues and stacks as examples, Generating fast indulgent algorithms, The topology of look-compute-move robot wait-free algorithms with hard termination, What Can be Computed in a Distributed System?, Weak symmetry breaking and abstract simplex paths, An Inductive-style Procedure for Counting Monochromatic Simplexes of Symmetric Subdivisions with Applications to Distributed Computing, An Introduction to the Topological Theory of Distributed Computing with Safe-consensus, An impossibility about failure detectors in the iterated immediate snapshot model, On the road to the weakest failure detector for \(k\)-set agreement in message-passing systems, Strong order-preserving renaming in the synchronous message passing model, Strongly terminating early-stopping \(k\)-set agreement in synchronous systems with general omission failures, Unnamed Item, Unnamed Item, Unnamed Item, New combinatorial topology bounds for renaming: the lower bound, Anti-\(\Omega \): the weakest failure detector for set agreement, Narrowing Power vs. Efficiency in Synchronous Set Agreement, Generalized Symmetry Breaking Tasks and Nondeterminism in Concurrent Objects, Untangling Partial Agreement: Iterated x-consensus Simulations, Wait-freedom with advice, A topological treatment of early-deciding set-agreement, A dynamic epistemic logic analysis of equality negation and other epistemic covering tasks, Wait-free approximate agreement on graphs, A distributed computing perspective of unconditionally secure information transmission in Russian cards problems, From adaptive renaming to set agreement, The Complexity of Early Deciding Set Agreement: How can Topology help?, An Axiomatic Approach to Computing the Connectivity of Synchronous and Asynchronous Systems, Topological Properties of Event Structures, Sheaves and Geometric Logic and Applications to Modular Verification of Complex Systems, A topological perspective on distributed network algorithms, A lower bound on the number of opinions needed for fault-tolerant decentralized run-time monitoring, Classifying rendezvous tasks of arbitrary dimension, Generalized Universality, Locality and Checkability in Wait-Free Computing, Oblivious Collaboration, Asynchronous Coordination Under Preferences and Constraints, t-Resilient Immediate Snapshot Is Impossible, Contention-related crash failures: definitions, agreement algorithms, and impossibility results, Narrowing power vs efficiency in synchronous set agreement: relationship, algorithms and lower bound, Unnamed Item, Back to the Coordinated Attack Problem, Simultaneous Consensus vs Set Agreement: A Message-Passing-Sensitive Hierarchy of Agreement Problems