@oantolin @screwlisp @nosrednayduj @mdhughes @kentpitman @chiply @northernlights

That’s a great book! Herlihy, a leading light in distributed algorithms, explains how you can talk about a protocol as a continuous transformation on simplicial complexes.

Each vertex of the collection represents a (node, state) pair. An asynchronous message arrival creates more (node, state*) pairs, but in an additive sense (the old/original state persists in the collection, too, because the message maybe just hasn’t arrived yet).

A CGI analogy: a message arrives, and the vertex turns into more polygons, the image gets more detailed. But! “more detailed” has a couple of constraints: you don’t see a hole that wasn’t there before, and a void that was there doesn’t get filled in, and a gap or crack doesn’t appear between your new polygons. The topological structure doesn’t change.

So: basically, you produces impossibility proofs by showing that the starting algorithmic state represents one structure (a connected one, for example) and the end state represents a different structure (disconnected). There’s no set of transformations (corresponding to messages) that can get you from one structure to the other.

This turns the states reachable by distributed algorithms into topological structures, and algebraic topologists have all kinds of tools to help you.