Dijkstra award 2008 goes to ‘Sparse Partitions’ at Paper Trail: "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."
