Jason (jcreed) wrote,

Richard Lipton has a great blog post about surprises in mathematics, which links to an interesting paper: "Algebraic Topology and Distributed Computing: A Primer".

I already knew thanks to Goubault and many others that directed topologies have something to do with concurrency but this appears to be something different. The idea is that the state space of a distributed consensus algorithm can be represented by a plain old garden-variety simplicial complex, and proofs of algorithmic impossibility results can be squeezed out of topological nonembeddability results. And we have plenty of power tools for showing that one space can't be embedded in the other: just look at the homology groups of the spaces in question!

What's dawning on me is that the really interesting thing about this work (and also the Goubault/Fajstrup/et alia. concurrency stuff) is that there is another way of "ascending the dimensional ladder" besides the "usual" one given my background. The "usual" way is that objects (0-cells) are types, morphisms (1-cells) are programs/expressions/terms, morphisms-between-morphisms (2-cells) are reductions/rewrites, 3-cells are rewrites from one "story of how I rewrote the term" to another, and so on.

The "new" way is that you have a high-dimensional picture because you have multiple concurrent processes.

In the ATaDC paper above, vertices are final process states (pairs consisting of a unique process id and a value the process eventually outputs) and edges (and faces, and higher simplices) are compatibility relations that say "this collection of outputs can simultaneously obtain". Having n processes means you may want to have up to (n-1)-dimensional simplices. In the world of Goubault/Fajstrup/et al., each process has a little timeline along which it moves, and having n processes means that you have an n-dimensional picture of what's reachable along everyone's timeline.

So these two aren't quite the same picture --- they're "off by one" in one sense --- but they're obviously similar, too.
Tags: distributed systems, math, topology

  • (no subject)

    Played some board games at the fb office with newly-arrived-to-nyc dan blandford and some friends-of-friends of his. Codenames and…

  • (no subject)

    This morning I suddenly had a memory of a game I used to play in the mid-late 90s over email. In it you "designed" animals by giving them, like, 4…

  • (no subject)

    Played some more Shenzhen I/O. The later puzzles are getting straight up hard. Had some fun optimizing the earlier ones, though.

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded