ECE 559BH: SPRING 2006 Problem set 1 Solutions
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.
Credit: 4 graduate hours
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
Tentative summary of Topics:
Selected References:
Topics in Communications: Distributed Network
Algorithms
Problem set 2 Solutions
Problem set 3 Solutions
Problem set 4 Solutions
Problem set 5 Solutions
Midterm Solutions
Final Solutions
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