TDS Seminar: Network Coding for Adversarial Dynamic Networks
Theory of Distributed Systems 2010/2011
Speaker: Bernhard Haeupler
Speaker Affiliation: MIT
Host: Nancy Lynch
Host Affiliation: MIT

Date: 4-30-2010
Time: 12:00 PM - 1:00 PM
Location: 32-G631

Abstract:

We give new algorithms for k-Token Dissemination and Counting in the highly
dynamic network model of Kuhn, Oshman and Lynch in which a highly adaptive
adversary is allowed to choose a different (connected) topology at every
time
step.

Heart of our algorithms are efficient broadcasting protocols based on random
linear network coding (RLNC). We give a novel, simple and powerful technique
to analyze the convergence time of these protocol and show how to use this
technique to proof that that for reasonably big packet sizes the RLNC
broadcast succeeds in information-theoretic (order) optimal time.
We use the RLNC algorithm to achieve faster Counting protocols and give new
insights in how to exploit interval connectivity and related stability
measures more efficiently.