CSL Master Calendar

Back to Listing

Communications/ICWS Seminar: "Analyzing Network Coding Gossip Made Easy"

Event Type
Coordinated Science Laboratory
141 Coordinated Science Laboratory
Jan 14, 2013   4:00 pm  
Mr. Bernhard Haeupler, Computer Science & Artificial Intelligence Lab, Massachusetts Institute of Technology
Originating Calendar
CSL Communications Group Calendar

This talk will introduce projection analysis - a new technique to analyze gossip protocols that are based on random linear network coding (RLNC). The analysis shows that RLNC gossip achieves 'perfectly pipelined' convergence times of O(k + T), where k is the number of messages to be distributed and T is the time it takes to disseminate one message. The analysis is extremely simple yet applies and extends to a wide variety of network settings. The first such extension the talk will touch upon are highly dynamic networks in which the topology can change completely at any time. Virtually nothing besides simple O(kT) sequential flooding protocols was previously known for such a setting. The second extension covered in the talk shows that RLNC continues to perform optimally even if only a finite amount of memory is used for coding. This leads to new, highly efficient network coding protocols with high practical potential.

link for robots only