## Department of Electrical and Computer Engineering

### ECE 559BH: SPRING 2006 Topics in Communications: Distributed Network Algorithms

Description: The course will juxtapose several topics loosely related to communication in large networks such as the Internet, and distributed coordination. The behavior of distributed network protocols, such as those for peer-to-peer networking, will be studied through the use of stochastic analysis methods. Forward error correction, such as digital fountain codes, and, more generally, network coding, are based on stochastic methods. One general application the course will focus on is simply the communication or storage of files. Another application is the problem of distributed scheduling or reservation of resources. The distributed nature of the applications, with tens, thousands, or even millions of interacting agents, suggests that ideas of game theory and mechanism design are relevant. Each student will be expected to give two 40-minute presentations of material during the semester. Grades will be based on homework (10%), classroom presentations by students (30%), a midterm and final exam (30%), and a project (30%).

Prerequisites: ( ECE 534: Random processes or Math 466: Probability II ) and CS 473: Algorithms, or consent of instructor.

Assigned Reading: Selected journal articles and portions of texts. There will be no required text, although the book R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995, is recommended.

Meeting times: 1:00-2:30 p.m. TuTh in 336 Mechanical Engineering Building

Instructor: Professor Bruce Hajek

Office hours: Wednesday and Friday, 3-4 p.m. in Room 105 CSL

Lecture Schedule
 Date Speaker(s) Topic Reference 1/17 BH Balls in bins: birthday surprise, maximum load, Poisson heuristic and associated bound Mitzenmacher and Upfal, Chapter 5 (Motwani and Raghavan, Chapter 3.6, covers much of same) 1/19 BH Balls in bins: coupon collector's problem, Poisson heuristic and associated bound See reading for 1/17 1/24 BH Chord lookup system I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, "Chord: a scalable peer-to-peer lookup service for Internet applications" 1/26 Srinivas Shakkottai BitTorrent file distribution system Bram Cohen, "Incentives build robustness in BitTorrent." (5 pages) Mimeo, May 22,2003, and BitTorrent protocol specification (3 pages) on BitTorrent.com D. Qiu and R. Srikant "Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer Networks, Proc. ACM SIGCOMM, Portland, OR, Sept. 2004. 1/31 BH Martingales -- conditional expectation, sigma algebras, general definition of a martingale, examples References for martingale material: basic martingale theory: G.R. Grimmett and D.R. Stirzaker's treatment of martingales (Sections 7.7-7.10 & Chapter 12). (also, James R. Norris has posted some notes from his advanced probability course.) Azuma-Hoeffding and the method of bounded differences: Mitzenmacher and Upfal, Chapter 12 and Section 4.4 of Motwani and Raghavan. 2/2 Lei Ying slides Distributed function computation R.G. Gallager, "Finding parity in a simple broadcast network," IEEE Trans. Info. Theory , vol. 34, March 88, pp. 176-180. E. Kushilevitz and Y. Mansour, "Computation in noisy radio networks," Proc. Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 1998, pp. 236-243. Related: N. Goyal, G. Kindler, and M. Saks, "Lower-bounds for the noisy broadcast model, and for the generalized noisy-decision trees," BH Martingales -- Azuma-Hoeffding concentration inequalities See reading for 1/31 2/7 BH Martingales -- method of bounded differences and examples See reading for 1/31 2/9 BH Martingales -- stopping times See reading for 1/31 2/14 Xiaolan Zhang notes & Ramakrishna Gummadi Random online algorithms R. Motwani and P. Raghavani, Portions of Chapter 3, and Sections 13.1 - 13.3. 2/16 Ramakrishna Gummadi (continuation) the Marker algorithm for paging See 2/14 BH Martingales -- uniform integrability and optional sampling theorems See reading for 1/31 2/21 Serdar Yuksel notes Martingale methods for stability of Markov processes Intro Markovian Processes: James Norris (sections 1.5 and 1.7) link Comparison theorem: S.P. Meyn and R.L. Tweedie, Markov Chains and Stochastic Stability, (Chapters 11-14) link 2/23 Serdar Yuksel (continued) Two applications of comparison theorem: Foster's criteria, bounding moments See 2/21 for reading BH Martinagales -- applications to algorithms See reading for 1/31 2/28 BH Martinagales -- applications to algorithms See reading for 1/31 Sichao Yang Randomized algorithms for Byzantine agreement For deterministic algorithm: M. Pease, R. Shotak, L. Lamport, Reaching Agreement in the Presence of Faults," JACM 27, 2 (April 1980) link For random algorithm: R. Motwani and P. Raghavani, Randomized Algorithms , Section 12.6 3/2 Sichao Yang Byzantine agreement (continued) See 2/28 for reading 3/7 BH LT codes - introduction, derivation of soliton and robust soliton distribution M. Luby, "LT Codes," Proc. IEEE Stoch. 2002 (On IEEE Xplore) Chapter 50 of D. J. C. MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, Cambridge, 2005. link 3/9 BH LT codes - exact computatation for Poisson distribution E. N. Maneva and A. Shokrollahi, "New model for rigorous analysis of LT-codes," ArXiv, December 8, 2005. link 3/14 BH LT codes - proof of performance for finite graphs Luby's LT codes paper, see 3/7 3/16 BH LT codes -asymptotic performance Maneva and Shokrollahi (see 3/9) also discuss an asymptotic analysis based on R. W. R. Darling, J. R. Norris, "Structure of large random hypergraphs," Annals of Applied Probability 2005, Vol. 15, No. 1A, 125-152. link 3/28 BH Raptor codes Amin Sholrollahi, "Raptor Codes," To appear in IEEE Transactions on Information Theory, 2006. . link to earlier version link to December 2005 slides 3/30 midterm exam 4/4 Srinivas Shakkottai slides network coding approach to gossip S. Deb and M. M\'edard, Algebraic gossip: a network coding approach to multiple rumor mongering," Allerton Conference , 2004. Christos Gkantsidis, Pablo Rodriguez, "Network coding for large scale content distribution", IEEE/INFOCOM 2005 , Miami. March 2005. link 4/6 BH Averaging in a network with given topology by gossip S. Boyd, A. Ghosh, B. Prabhakar, D. Shah, "Gossip, analysis and applications," IEEE INFOCOM 2005 and journal version link 4/11 Xiaolan Zhang notes VCG allocation mechanism for auction of goods D. Lehmann, L.L. O’Callaghan, and Y. Shoham, “Truth revelation in approximately efficient combinatorial auctions,” J. of the Association for Computing Machinery, vol. 49, 5, September 2002, 577-602. link 4/13 Xiaolan Zhang Truthful mechanisms with approximate optimization See reading for 4/11 BH Truthful randomized auction S. Dobzinski, N. Nisan, and M. Schapira, "Truthful randomized mechanisms for combinatorial auctions" To appear in STOC 2006. link 4/18 Ramakrishna Gummadi slides The probabilistic method Mitzenmacher and Upfal, Chapter 6 4/20 Lei Ying slides The classical gossip process Section 5 of A. M. Frieze and G. R. Grimmett, "The shortest-path problem for graphs with random arc-lengths, Discrete Applied Mathematics , Vol 10, January 1985, Pages 57-77. link 4/25 Serdar Yuksel Belief propagation, with emphasis on convergence F.R. Kschischang, B. J. Frey, H.-A. Loeliger, "Factor Graphs and the Sum-Product Algorithm," IEEE Trans. Info. Theory, Feb 2001. S. C. Tatikonda, "Convergence of the sum-product algorithm," IEEE ITW April 2003. J. S Yedidia, W. T. Freeman and Y. Weiss, "Constructing Free Energy Approximations and Generalized Belief Propagation ALgorithms," IEEE Trans. Info. Theory, July 2005. 4/27 Sichao Yang Scheduling with deterministic constraints, Cruz's SCED algorithm, pricing aspects Pages 73-80 of notes for ECE 567 link 5/2 BH Coding and/or queuing in packet networks D.S. Lun, M. Medard, R. Koetter, and M. Effros, "On coding for reliable communication over packet networks" (on Arxiv.org, October 2005) link S. Bhadra and Sanjay Shakkottai, "Looking at large networks: coding vs. queueing," IEEE INFOCOM 2006, April 2006 link

Tentative summary of Topics:

• I. Distributed algorithms for information dissemination and storage (16 hours)
• Gossip algorithms (algorithms for computation and information exchange in an arbitrarily connected network, including both store-and forward and network coding approaches
• Peer-to-peer systems: principal algorithms, distributed file systems, and distributed backup
• Implementation tricks: hash functions and Bloom filters
• Digital fountain codes
• Randomized online algorithms
• Randomized algorithms for the agreement problem
• II. Distributed mechanism design, including how to make greed work in networks (11 hours)
• Mechanisms for distributed scheduling and coordination
• A few concepts from game theory and auctions
• III. Stochastic techniques (for analysis of interacting random systems, such as random algorithms or algorithms in a random graph). (16 hours)
• Martingale convergence and concentration methods
• Branching processes
• Poisson clumping method
• Moment method
• Mixing and conductance of Markov chains
• Analysis by scaling and ordinary differential equations (fluid analysis)

Selected References:

• Bloom filters and hashing functions
• Andrei Broder and Michael Mitzenmacher, Network applications of Bloom filters: A Survey", Allerton Conference, 2002. link
• J. Byers, J. Considine, M. Mitzenmacher, and S. Rost Informed Content Delivery Across Adaptive Overlay," SIGCOMM02, August, 2002. link
• M. Mitzenmacher and U. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis , Cambridge University Press, Cambridge, 2005. (On reserve in Grainger Enginering Library)
• Digital fountain codes
• D. J. C. MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, Cambridge, 2005. link
• Gossip algorithms
• A.M. Frieze and G.R. Grimmett, The shortest path problem for graphs with random arc-lengths," Disc. Appl. Math , 10, (1985) 57-77.
• S. Deb and M. M\'edard, Algebraic gossip: a network coding approach to multiple rumor mongering," Allerton Conference , 2004.
• Christos Gkantsidis, Pablo Rodriguez, "Network coding for large scale content distribution", IEEE/INFOCOM 2005 , Miami. March 2005. link
• lA. Dimakis, A.D. Sarwate, and M.J. Wainwright, Geographic gossip: efficient aggregation for sensor networks,'' link
• S. Boyd, A. Ghosh, B. Prabhakar, D. Shah, "Gossip, analysis and applications," IEEE INFOCOM 2005 and journal version link
• Peer to peer systems
• I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications." Proceedings of the ACM SIGCOMM 2001 Conference , August, 2001. San Diego, CA.
• Yatin Chawathe, Sylvia Ratnasamy, Lee Breslau, and Scott Shenker, Making Gnutella-like P2P Systems Scalable," SIGCOMM 2003 . August 2003. Karlsruhe, Germany.
• Alberto Blanc, Yi-Kai Liu, Amin Vahdat Designing Incentives for Peer-to-Peer Routing," Workshop on Economics of Peer-to-Peer Systems June 2004
• Stefan Saroiu, P. Krishna Gummadi, and Steven D. Gribble. Exploring the Design Space of Distributed and P2P Systems," Proceedings of the First International Workshop on Peer-to-Peer Systems (IPTPS '02). March 2002. Cambridge, MA.
• Probabilistic tools
• R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge Univ Press, 1995. (On reserve in Grainger Enginering Library)
• G.R. Grimmett and D.R. Stirzaker, Probability and Random Processes (3rd ed.) , Oxford Univ Press, 2001.
• D. Williams, Probability with Martingales, Cambridge University Priess, 1991.
• S.N. Ethier and T.G. Kurtz, Markov Processes: Characterization and Convergence , Wiley, 1986.
• D. Aldous, Probability Approximations via the Poisson Clumping Heuristic , Springer, New York, 1989.
• H. Cohn, A martingale approach to supercritical branching processes," Ann. Probab . 13, 1179 -- 1191, 1985.
• M. Jerrum and Alistar Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration," Chapter 12
• N. Alon and J. Spencer, The Probabilistic Method (2nd ed.), Wiley, 2000.
• Game theory and mechanism design
• Drew Fudenberg and Jean Tirole. Game Theory , MIT Press, 1991
• Noam Nisan and Amir Ronen. Algorithmic Mechanism Design," Games and Economic Behavior, 35:166-196, 2001.
• J. Shneidman, D. Parkes, and L. Massoulie, Faithfulness in internet algorithms," Proc. SIGCOMM Workshop on Practice and Theory of Incentives and Game Theory in Networked Systems (PINS'04) , Portland, OR, USA, Sept. 2004. link
• D. Lehmann, L.L. O’Callaghan, and Y. Shoham, “Truth revelation in approximately efficient combi- natorial auctions,” {\em J. of the Association for Computing Machinery,} vol. 49, 5, September 2002, 577-602.