Asynchronous Computability

Asynchronous Computability Links

• Algebraic Topology and Concurrency Directory of reports applying methods in algebraic topology to concurrent computation, following the approach of Herlihy and Shavit. Maintained by Stefan Sokolowski.
  
• The Part-Time Parliament Technical report by Leslie Lamport characterising a reliability issue in distributed networks in terms of a fictional parliament's consitution.
  
• Linearizable Counting Networks Article by Herlihy and Shavit which characterises the complexity of classes of counting problem depending upon whether they are linearisable.
  
• A Primer on Algebraic Topology and Distributed Computing Introductory article by Herlihy and Rajsbaum on applications of algebraic topology to distributed computation.
  
• A Historical Note on `Geometry and Concurrency' Online report by Eric Goubault, surveying the field from its prehistory in terms of classical interleaving and non-interleaving analyses of concurrency, through to modern applications of simplicial sets to fault tolerant computation.
  
• The Topological Structure of Asynchronous Computability Article by Herlihy and Shavit, which shows how characterising asynchronous computation as simplicial complexes in algebraic topology is a powerful abstraction, which they apply to the solution of several open problems in the field. Written in 1993, this paper is already a classic.