TDS Seminar: Network Coding for Adversarial Dynamic Networks
Speaker: Bernhard Haeupler , MIT
Date: April 30 2010
Time: 12:00PM to 1:00PM
Location: 32-G631
Host: Nancy Lynch, MIT
Contact: Rotem Oshman, rotem@csail.mit.edu
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.
See other events that are part of Theory of Distributed Systems 2010/2011
See other events happening in April 2010
