### Page Content

The workshop takes place on Wed July 20, 2011, at Ernst Reuter Platz 7, TEL 20, Berlin!

Host and contact for more information: Stefan Schmid

Time | Speaker | Title |
---|---|---|

09:30–10:45 | Roger Wattenhofer, ETH Zürich | Theory Meets Practice: It’s about Time |

10:45–12:00 | Andréa Richa, Arizona State University | Jamming-Resistant Wireless Network MAC Protocols |

12:00–13:30 | Lunch break | |

13:30–14:45 | Christian Scheideler, Universität Paderborn | Approximate Duality of Multicommodity Multiroute Flows and Cuts |

All talks will take place in Auditorium 3 (TEL 20), Ernst-Reuter-Platz 7, 10555 Berlin. |

## Roger Wattenhofer, "Theory Meets Practice: It’s about Time"

**Abstract:**

Having a common notion of time is a basic building block in many networks and distributed systems. In sensor networks, for instance, time synchronization is needed for locating events by trilateration, or for establishing an efficient media access control. The problem is well-studied, both in theory and practice. Nevertheless, several researchers have experienced and reported problems when trying to establish a common notion of time even in mid-scale networks. And also theoreticians all of a sudden started studying the problem again. In my talk, I will discuss clock synchronization from a theoretical point of view (published at FOCS, PODC, and JACM), as well as from a practical point of view (published at IPSN and SenSys). Hopefully I can surprise the audience with some unexpected impossibility results, and new protocols that improve the state of the art considerably. As such clock synchronization may serve as a good example where theory meets practice. I hope that the talk will be interesting to researchers with different backgrounds, such as networking, distributed systems, algorithms, or control theory.

Talk slides**Bio:**Roger Wattenhofer is a full professor at the Information Technology and Electrical Engineering Department, ETH Zurich, Switzerland. He received his doctorate in Computer Science in 1998 from ETH Zurich. From 1999 to 2001 he was in the USA, first at Brown University in Providence, RI, then at Microsoft Research in Redmond, WA. He then returned to ETH Zurich, originally as an assistant professor at the Computer Science Department. Roger Wattenhofer's research interests are a variety of algorithmic and systems aspects in computer science and information technology, currently in particular wireless networks, multi-core systems, peer-to-peer computing, and social networking. He publishes in different communities, distributed computing, networking, and theory/algorithms.

## Andréa Richa, "Jamming-Resistant Wireless Network MAC Protocols"

**Abstact:**

We consider the problem of designing local-control medium access control (MAC) protocols for wireless networks that are provably robust against adaptive adversarial jamming. Our protocols, since they run at the MAC payer, are orthogonal to physical layer protocols that rely on a broad spectrum (e.g., spread spectrum and frequency hoping protocols), and can be used in conjunction with those or in networks where a broad spectrum is not available (e.g., sensor networks). We present a summary of our work in this area, going from single-hop wireless networks to multihop wireless networks modeled under SINR (signal-to-noise ratio model), and from more standard adaptive adversarial models for the jammer(s) to a more realistic adversarial model where, in addition to knowing the protocol and its entire history, the jammer also has some knowledge about the action of the nodes at the current time step. Our protocols are energy efficient, and require only very limited amount of knowledge about the jammer. We also show how to extend our protocol to obtain a fair use of the wireless channel and a robust and efficient protocol for leader election. We also present simulation results that further validate our theoretical bounds.*This is joint work with Christian Scheideler (University of Paderborn, Germany), Stefan Schmid (TU Berlin), Jin Zhang (ASU), and Baruch Awerbuch (John Hopkins University).*

Talk slides**Bio:**

Prof. Andrea W. Richa is an Associate Professor in Computer Science and Engineering at Arizona State University. She joined Arizona State in August 1998. Prof. Richa received her M.S. and Ph.D. degrees from the School of Computer Science at Carnegie Mellon University, in 1995 and 1998, respectively. She also earned an M.S. degree in Computer Systems from the Graduate School in Engineering (COPPE), and a B.S. degree in Computer Science, both at the Federal University of Rio de Janeiro, Brazil, in 1992 and 1990, respectively. Prof. Richa's main area of research is in network algorithms. For more information, please visit http://www.public.asu.edu/~aricha.

## Christian Scheideler, "Approximate Duality of Multicommodity Multiroute Flows and Cuts"

**Abstract:**

Given an integer *h*, a graph* G=(V,E)* and *k* pairs of vertices, an *h*-route cut is a subset *F* of *E* such that after the removal of *F* none of the pairs is connected by *h* edge-disjoint paths. Finding the minimum *h*-route cut is a natural generalization of the classical mincut problem for multicommodity flows (take *h=1*). I will show that there is a *polylog(k)*-approximation algorithm for the minimum *h*-route cut problem for any constant *h* which implies an approximate duality theorem for multiroute multicommodity flows and cuts. This answers an open problem posted in several previous papers which, until this year, were only able to solve the *h≤2* case. *This is joint work with Petr Kolman.*

Talk slides

**Bio: **

Christian Scheideler received his Computer Science Diploma in 1993, his PhD with distinction in 1996, and a German postdoc degree called Habilitation in 2000, all from the University of Paderborn in Germany. After his PhD he spent a year at the Weizmann Institute in Israel. He was an Assistant Professor at the Johns Hopkins University from 2000 to 2005, then an Associate Professor at the Technical University of Munich, and since 2009 he is a Full Professor at the University of Paderborn. Christian Scheideler has co-authored close to 100 research papers in the area of algorithms, networks, and distributed systems. He has served on the editorial board of various journals and on the program committees of many conferences. His current research interests include distributed algorithms and data structures, secure distributed systems, network theory, randomized algorithms, and discrete mathematics.