Random Hamiltonian Cycles and Real-Time Streaming in Peer-to-Peer Networks

Peer-to-peer networks are networks without a massive central server. Instead, each peer in the network transmits the data it receives to a subset of other peers in the network, thus propagating information in the network.  We will illustrate the application of random graphs to the problem of designing simple distributed algorithms for peer-to-peer streaming applications (such as live video) that can achieve high throughput and low delay, while maintaining a very small neighbor set for each peer. The talk will be based on joint work with Joohwan Kim.