### 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
[1]

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

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

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

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

13:30–14:45 | Christian
Scheideler [4], 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 [5]**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 [6]**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
[7].

## 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 [8]

**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.

## Speakers

- Roger Wattenhofer, ETH Zürich [9]
- Andréa Richa, Arizona State University [10]
- Christian Scheideler, Universität Paderborn [11]

rsonen/scheideler.html

LS_Workshop_2011/2011-07-20-wattenhofer.pdf

LS_Workshop_2011/2011-07-20-richa.pdf

LS_Workshop_2011/2011-07-20-scheideler.pdf

ersonen/scheideler.html