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: Joanne Hanley, 617-253-6054, joanne@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
