Congratulations to the Best Paper Award winners!

Pierre Fraigniaud (University Paris Diderot )
"On the role of identities in local distributed computing"

It is a pleasure to award the 2014 SIROCCO Prize for Innovation in Distributed Computing to Pierre Fraigniaud. The prize is awarded for his contribution to the understanding of routing in small world models and social networks, and to the understanding of the trade - offs between information and efficiency in routing in general.

Pierre’s contribution to research and his innovation in distributed computing are by now well-known and well documented. His work and publications in our community range from routing and labeling problems, mobility, exploration and information spreading, to wireless networks, and from algorithms to lower bounds. Moreover, this is just a partial list. In particular, Pierre has had a large impact on the research into problems of using information for routing. For example, he dealt with compact routing tables (and more generally, with compact distributed data structures) starting with an early paper in SIROCCO’98 [7], and later in other conferences. Another related example is his work on distributed search.

Out of Pierre’s rich contributions to routing, we would like to concentrate on his contribution to routing in social networks. The phenomenon of small worlds was investigated originally in a sociological context (see the famous work of Milgram), rather than in the realm of mathematics or distributed computing. Kleinberg has shown that specific graphs could be enhanced to show this phenomenon. That is, not only did the enhanced graph enjoy a small diameter, but also it was easily navigable. Others have later shown a similar phenomenon for other graphs. One could have suspected that this was a general phenomenon of graphs, unrelated to the sociological context.

In a series of papers [1]-[6] Pierre, with his various coauthors, succeeded in defining the conditions necessary for a graph to become navigable. In particular, the small world phenomenon is not a universal property of any graph. On the other hand, he brought evidence supporting the claim that this is an inherent property of social networks. As Pierre showed in his paper “A Doubling Dimension Threshold Θ(log log n) for Augmented Graph Navigability” [1], not every graph could be augmented in such a way that it can become navigable. Then, around 2010, Pierre’s paper, “On the searchability of small-world networks with arbitrary underlying structure” [5], presented an optimal algorithm for navigation in any graph and analyzed the exact performance of the algorithm. The result of the paper answered the question of navigability in general graphs. As this paper showed, there is a gap between general graphs and social networks. In his SIROCCO paper [3], Pierre also suggested how to test the model of social augmentation. This paper took the ideas of navigability and augmentation of social networks from a mathematical model to a practical big data application by asking how to verify the theory of navigability by augmentation. This paper bridged the boundary between theory and measurement in the real world. Pierre’s results have had a profound impact on the field of social networks and on connecting this field to the field of distributed computing.

1. Fraigniaud, P., Lebhar, E., Lotker, Z.: A Doubling Dimension Threshold Θ(loglogn) for Augmented Graph Navigability. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 376–386. Springer, Heidelberg (2006)
2. Fraigniaud, P., Gavoille, C., Kosowski, A., Lebhar, E., Lotker, Z.: Universal augmentation schemes for network navigability: overcoming the sqrt(n)-barrier. In: SPAA 2007, pp. 1–7 (2007)
3. Fraigniaud, P., Lebhar, E., Lotker, Z.: Recovering the Long-Range Links in Augmented Graphs. In: Shvartsman, A.A., Felber, P. (eds.) SIROCCO 2008. LNCS, vol. 5058, pp. 104–118. Springer, Heidelberg (2008)
4. Fraigniaud, P., Giakkoupis, G.: The effect of power-law degrees on the navigability of small worlds: [extended abstract]. In: PODC 2009, pp. 240–249 (2009)
5. Fraigniaud, P., Giakkoupis, G.: On the searchability of small-world networks with arbitrary underlying structure. In: STOC 2010, pp. 389–398 (2010)
6. Fraigniaud, P.: A New Perspective on the Small-World Phenomenon: Greedy Routing in Tree-Decomposed Graphs. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 791–802. Springer, Heidelberg (2005)
7. Fraigniaud, P., Gavoille, C.: A Theoretical Model for Routing Complexity. In: SIROCCO 1998, pp. 98–113 (1998)