2008 Edsger W. Dijkstra Prize Paper

I saw mention today of the 2008 Edsger W. Dijkstra Prize. The winner was a 1990 paper which I remember reading and discussing in the early days of JXTA. The relevance to JXTA was in how it helped routing and validated P2P multihop routing as being capable of near optimal performance.

PaperTrail Summary:
...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.
Comments:

Post a Comment:
Comments are closed for this entry.
About

mduigou

Search

Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today