Not sure why I didn’t post this when I first found out – the Djikstra 2008 prize for an outstanding and influential paper in distributed systems has been awarded to David Peleg and Baruch Awerbuch for their 1990 FOCS paper *Sparse Partitions* (on-line copy available from MIT ad-hoc algorithms course here).

The citation does a much better job than I could of explaining the paper’s relevance. The general idea is that the authors show that there are efficient ways of constructing clustered representations of graphs that remain within a small factor of the original in terms of route lengths. Further, the authors show that this can be done in a distributed manner. This has lots (and lots) of potential applications – the typical example is for a compact routing scheme, where nodes can store smaller routing tables between clusters rather than between nodes.

I’ve got the paper cued up on my list of walkthroughs to write, so expect a better explanation than the one above soon.