December 2nd, 2012

beartato phd

(no subject)

Having a really sleepy hazy sort of day, but found a couple of magnificent papers from the 90s about connections between distributed systems and geometry.
The Topological Structure of Asynchronous Computability, Herlihy and Shavit '93, which establishes the relationship between topology of simplicial complexes with vertices labelled by natural numbers 1 through n allowing for repetition of the same number at different vertices, and the dynamics of distributed systems with n processors. Then you get to
Three-processor tasks are undecidable, Gafni and Koutsoupias '99.
which takes this topological perspective, and brings out a real bummer for the analysis of distributed systems even with finite input and output types: the wait-free computability of such a function is undecidable if you have at least three participants.

And this is because determining what topological space you're really looking at is undecidable if all you're given is a triangulation (i.e. all the 2-simplices) of its interior. (Turns out we care about the 2-simplices, because a 2-simplex has three vertices, which correspond to the three participants that the theorem shows to suffice for undecidability)

And this is because determining what topological space you're really looking at depends on solving "the word problem" for groups, because you can represent any group as a 2-d simplicial complex: you have one vertex, and throw in an edge for every element of the group, and a triangle with edges a, b, c for every equation a * b = c that holds.

And the word problem is undecidable because (I think this is the reason?) you can build reversible universal Turing machines, and the question of whether some word over the group is equivalent to the identity is the same as the question of whether the Turing machine halts.

I'm just impressed at the staggering tower of abstractions on display in this result.