The Taub Faculty of Computer Science Events and Talks

A spanner of a given graph is a sparse subgraph that approximately preserves distances. Since their introduction in the late 1980's, spanners have found numerous applications in synchronization problems, information dissemination, routing schemes and more. Many applications of spanners are in computer networks, where the network needs to find a spanner for its own communication graph. We present distributed algorithms for constructing additive spanners in networks of bounded message size, namely in the CONGEST model. In addition, we present an innovative technique for showing lower bounds for constructing spanners in this setting, a technique that can be useful for other distributed graph problems. This is a part of my phd work, which concentrates on computing distances in distributed systems. Based on joint works with Keren Censor-Hillel, Telikepalli Kavitha, Noam Ravid and Amir Yehudayoff