The topological structure of asynchronous computability
From MaRDI portal
PL-topology (57Q99) Distributed systems (68M14) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Parallel algorithms in computer science (68W10)
Recommendations
- Computable obstructions to wait-free computability
- A simple constructive computability theorem for wait-free computation
- Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
- The Combinatorial Structure of Wait-Free Solvable Tasks
- Distributed computing through combinatorial topology
Cited in
(only showing first 100 items - show all)- A topological treatment of early-deciding set-agreement
- From adaptive renaming to set agreement
- Classifying rendezvous tasks of arbitrary dimension
- Narrowing power vs efficiency in synchronous set agreement: relationship, algorithms and lower bound
- Collapsibility of read/write models using discrete Morse theory
- An algorithmic approach to the asynchronous computability theorem
- Shared-object system equilibria: delay and throughput analysis
- Geometric and combinatorial views on asynchronous computability
- Structure theory of flip graphs with applications to weak symmetry breaking
- From geometric semantics to asynchronous computability
- On the uncontended complexity of anonymous agreement
- Randomized k-set agreement in crash-prone and Byzantine asynchronous systems
- Anonymous obstruction-free (n,k)-set agreement with n-k+1 atomic read/write registers
- Partial synchrony based on set timeliness
- Renaming and the weakest family of failure detectors
- Gathering identical autonomous systems on a circle using stigmergy
- 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
- The topology of look-compute-move robot wait-free algorithms with hard termination
- A dynamic epistemic logic analysis of equality negation and other epistemic covering tasks
- Contention-related crash failures: definitions, agreement algorithms, and impossibility results
- Wanted dead or alive: epistemic logic for impure simplicial complexes
- Life beyond set agreement
- Waiting in concurrent algorithms
- A lower bound on the number of opinions needed for fault-tolerant decentralized run-time monitoring
- The \(k\)-simultaneous consensus problem
- On the computability power and the robustness of set agreement-oriented failure detector classes
- From wait-free to arbitrary concurrent solo executions in colorless distributed computing
- Of choices, failures and asynchrony: the many faces of set agreement
- Locality and checkability in wait-free computing
- Distributed computability: relating \(k\)-immediate snapshot and \(x\)-set agreement
- Agreeing within a few writes
- Generalized symmetry breaking tasks and nondeterminism in concurrent objects
- The read/write protocol complex is collapsible
- 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
- Asynchronous coordination under preferences and constraints
- t-resilient immediate snapshot Is impossible
- Using the topological characterization of synchronous models
- Simultaneous consensus vs set agreement: a message-passing-sensitive hierarchy of agreement problems
- An equivariance theorem with applications to renaming
- A generalized asynchronous computability theorem
- Generalized Universality
- Locality and checkability in wait-free computing
- Oblivious Collaboration
- The Combinatorial Structure of Wait-Free Solvable Tasks
- Beyond Lamport's Happened-before
- Tight bounds for asynchronous renaming
- Distributed universality
- Schlegel diagram and optimizable immediate snapshot protocol
- Asynchronous message orderings beyond causality
- scientific article; zbMATH DE number 7228882 (Why is no real title available?)
- Toward a Topological Characterization of Asynchronous Complexity
- A separation of \(n\)-consensus and \((n+1)\)-consensus based on process scheduling
- The computability of relaxed data structures: queues and stacks as examples
- The Iterated Restricted Immediate Snapshot Model
- The Committee Decision Problem
- The Weakest Failure Detector for Message Passing Set-Agreement
- Concurrent computing and shellable complexes
- The topology of distributed adversaries
- A non-topological proof for the impossibility of \(k\)-set agreement
- Power and limits of distributed computing shared memory models
- Three-Processor Tasks Are Undecidable
- scientific article; zbMATH DE number 1559574 (Why is no real title available?)
- Combinatorial Topology of the Standard Chromatic Subdivision and Weak Symmetry Breaking for Six Processes
- Bounds on the step and namespace complexity of renaming
- The renaming problem in shared memory systems: an introduction
- Topology of the immediate snapshot complexes
- A simple characterization of asynchronous computations
- Linear space bootstrap communication schemes
- An equivariance theorem with applications to renaming
- Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
- A homological theory of functions: nonuniform Boolean complexity separation and VC dimension bound via algebraic topology, and a homological Farkas lemma
- Back to the coordinated attack problem
- GPU schedulers: how fair is fair enough?
- Order out of chaos: proving linearizability using local views
- Parallel combining: benefits of explicit synchronization
- Characterizing asynchronous message-passing models through rounds
- Communication Complexity of Wait-Free Computability in Dynamic Networks
- Computable obstructions to wait-free computability
- Randomized two-process wait-free test-and-set
- Hundreds of impossibility results for distributed computing
- scientific article; zbMATH DE number 7407798 (Why is no real title available?)
- Sporadic solutions to zero-one exclusion tasks
- What can be computed in a distributed system?
- The topology of shared-memory adversaries
- 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
- The computability of relaxed data structures: queues and stacks as examples
- An asynchronous computability theorem for fair adversaries
- Untangling partial agreement: iterated \(x\)-consensus simulations
- Distributed computability in Byzantine asynchronous systems
- The relative power of composite loop agreement tasks
- Computing in the presence of concurrent solo executions
- Narrowing Power vs. Efficiency in Synchronous Set Agreement
- On the road to the weakest failure detector for k-set agreement in message-passing systems
This page was built for publication: The topological structure of asynchronous computability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3158560)
