Wait-free protocols: from discrete to topological semantics. Work in Progress

In distributed computing, the existence of protocols is a great issue. Since the first impossibility result [FLP85], this domain has borrowed more and more techniques from topology (use of connectiv-ity [BMZ88]), combinatorial topology (use of simplicial complexes [HS93]) and from algebraic topology (use of the fundamental group [HR03]). On the other hand, directed algebraic topology has been developed [FGR, Gra03, FRG06] in order to study deadlocks and scheduling in distributed settings. In this approach, the interleaving of actions is described in a continuous manner. We believe that the directed approach can play a role in the description of the intricate combinatorial structure of some tasks. That is why we explicit the intuitive relations between the combinatorial and the continuous approaches.