Please note that this is an approximate schedule, limited by Aravind's memory.
It does not correspond exactly with what happened in class, and does
not substitute for attending class!
The first several lectures cover probabilistic preliminaries, and
applications in distributed algorithms, wireless networks, data-stream
Lecture 1, 8/31:
Lecture 2, 9/2:
- Scope of class, focus on distributed algorithms and probabilistic
- Randomized algorithms versus probabilistic analysis;
- Examples of
randomized algorithms, including hashing (mod a random prime)
to decide equality using few bits and analysis,
data-stream computation, backoff
- Underlying reasons why randomization helps
(random constructions as pioneered by Erdos and Shannon,
von Neumann-like interpretation of algorithm as a zero-sum
game played against an adversary, sampling, and symmetry-breaking
in distributed computation);
- Recap of probability and expectation;
- Linearity of expectation, indicator random variables,
Lecture 3, 9/7:
- Probabilistic proof of Turan's theorem, simplification using
convexity, distributed implementation, and connection to wireless networks;
- Inclusion-exclusion, what happens
if we truncate it at odd vs. even terms, union bound;
- Random graphs: Erdos' construction of Ramsey graphs, the challenge of
explicit constructions of random-like graphs and codes,
network design, and models for massive networks such as the
Web-graph and social networks.
Lecture 4, 9/9:
- Why the expectation being small enough or large enough may not always
- Markov's inequality: proof, optimality in a certain sense, upper vs. lower
tail bounds, proof of union bound using Markov's inequality, the role of
- A glimpse of neighborhoods and interference in multihop wireless
networks, scheduling using Luby's vertex-coloring protocol
Lecture 5, 9/14:
- Higher moments, variance, standard deviation, intuition and
examples, Chebyshev's inequality;
- Applying Chebyshev's inequality to estimate the mean of
finite-variance random variables;
- Chebyshev-Cantelli, median always within mean plus/minus std. dev.;
- Motivation for the data-stream model;
- The "plus 1 / minus 1" trick: a "reduction" from the permanent to the
determinant, and the limitations of this reduction;
- [AMS99], computation of the F2 statistic.
Lecture 6, 9/16:
- Complete [AMS99], discuss error-probability reduction;
- Brief discussion of variants of the "plus 1 / minus 1" trick
that work better for the reduction from the permanent to the determinant;
- Discussion of rigorous randomized hashing versus hash
functions such as MD5;
- Review of finite fields, universal hashing.
Lecture 7, 9/21:
- k-wise independent random variables and constructions, brief allusion
to Reed-Solomon and BCH codes;
- Why 4-wise independence sufficient in [AMS99], k-th central moment,
tail bounds under limited independence;
- Jensen's inequality, Chernoff-Hoeffding bounds and behavior under
various regimes, application to sampling.
- Chernoff-Hoeffding bounds under different error-regimes: examples
including splitting graphs and occupancy problems with different mean loads
(and an alternative proof using direct counting);
- Random graphs in network design: degree, diameter, and
- Begin [LMR94] distributed packet-routing.
The next several lectures mainly cover distributed algorithms,
P2P systems, and overlay networks.
Lecture 8, 9/23:
Lecture 9, 9/28:
- Complete [LMR94] distributed packet-routing;
- Brief discussion of the work of Ostrovsky-Rabani and Scheideler;
- Overview of P2P and overlay networks;
- Begin discussion of Probabilistic Resilient Multicast (PRM) from
Lecture 10, 9/30:
- Complete almost all of main analysis of
discussion of associated useful probabilistic techniques.
Lecture 11, 10/05:
- Routers and input-queued switches, brief discussion of switch-scheduling
- Start algorithm of
[PS97], in a switch-scheduling and resource-allocation context.
Lecture 12, 10/07:
Guest Lecture by Prof. Bobby Bhattacharjee.
- Complete part of the analysis of
[PS97], by proving tail bounds for sums of negatively correlated random
- Introduction to Martingales, Martingale tail bounds, allusion to
- Start Chord from [SM+03].
Lecture 13, 10/12:
- Covered search in replication in P2P systems, including
Lecture 14, 10/14:
Lecture 15, 10/19:
- Continue discussion of Chord from [SM+03]: properties of the distribution
of peers on Chord ring, lookup time, behavior under node-additions,
- Start [KS04].
10/21: Mid-term, no lecture.
- Milgram's experiments and the Watts-Strogatz models;
- Kleinberg's "small world" approach [Kle00]: models, upper-bound for
inverse-square law, and intuition for why other powers do not work;
- A brief look at randomized P2P topologies such as Randomized Chord;
- Some of the main ideas behind "know thy neighbor's neighbor"
[MNW04], including routing in long-range percolation graphs and its analysis.
Lecture 16, 10/26:
Lecture 17, 10/28:
- P2P networks that are sensitive to network-distance: start
- Brief allusion to extensions of
[PRR99], including the main result of
- Further intuition and search algorithm of
- Unstructured P2P networks, the natural random-walk approach of
[GMS04], and relevant background on Markov Chains and random walks from
The next several lectures mainly cover wireless, ad hoc and
Lecture 18, 11/02:
Lecture 19, 11/04:
- Brief Guest Lecture by Prof. Ashok Agrawala on various (practical)
aspects of wireless networking, and on where the field may be headed;
- Finish up
[GMS04]: the role played by the second eigenvalue, expansion and
conductance, rapid mixing and the utility of even adjacent samples once we
have walked past the mixing time, and summary of the experimental work
in this paper;
[KDG03]: the basic setup, and Uniform Gossip.
Lecture 20, 11/09:
- Finish up some of the main ideas of
[KDG03]: the main result on the diffusion time of Uniform Gossip,
flooding and fault-tolerance, and general remarks on the role of the
L_2 norm (versus other L_p norms) in such potential-function arguments.
Lecture 21, 11/11:
- Start [CL+04]: sensor databases (e.g., the setting of TAG), aggregation
across multiple trees to guard against failures, idempotent /
duplicate-insensitive functions, counting multisets and implementation
of the Flajolet-Martin scheme, brief remarks on adding fault-tolerance to
- The first data-stream algorithm of
[BJ+02] for counting multisets;
- Start [BBC04]: the basic problem, issues with spatial sampling, min-wise
sampling, and random walks; the three key ideas of geographic routing
(especially GPSR), Voronoi diagrams, and von Neumann's rejection sampling.
Lecture 22, 11/16:
- Complete the discussion of the basic protocol of [BBC04].
- Overview of ad hoc networks from
[Raj02]: focus on applications, battery power, energy transmission, and
three models for interference (Physical Model, Protocol Model, and
Distance-Two Interference Model -- this last one is not covered in
- Degenerate/inductive graphs and inductive coloring; how Luby's algorithm
[Lu93] extends to such colorings;
- Review of ALOHA/Ethernet protocol and introduction to
Lecture 23, 11/18:
- ALOHA/Ethernet analyzed using stochastic domination, and
extension to networks;
- Start packet-scheduling on general disk graphs under distance-2
interference, from [KM+04]:
recap of Leighton-Maggs-Rao and why the standard definition of congestion
is not a good lower-bound here, more refined lower-bound and packing lemma,
start analysis of random-delays algorithm.
Lecture 24, 11/23:
Guest Lecture by Srinivasan Parthasarathy:
- Complete the discussion of disk-graph scheduling
- Cover the "cone-coverage" algorithm for topology control, due to
- A very brief introduction to information theory and coding theory:
basic definitions and the capacity of the binary symmetric channel.
- Covered some of the main (non-random-network) results of
from [GK00]: given an arbitrary (not random) network of area 1 x 1 with n
nodes and n arbitrary source-sink pairs, then the maximum concurrent
transport-throughput achievable is O(1/sqrt(n)); also, this
is achievable by an optimum placement of nodes and carefully choosing the
The next three lectures cover packet-marking for Internet security; Lecture
27 ends with network decomposition,
a simple and powerful primitive that is especially useful in
Lecture 25, 11/30:
Lecture 26, 12/02:
[Adl02]: background, the models considered, and full analysis of the case
"b = 1" for a single path of attack.
Lecture 27, 12/07:
- analysis of the case of general b for a single path of attack, in
the case of random initialization by the Attacker;
- intuition and examples for why b needs to be large as k increases;
- basic ideas behind protocol for general k.
Lecture 28, 12/09:
- Recap of basic ideas behind the protocol of
[Adl02] for general k;
- Network decomposition: applications and the distributed algorithm
- Brief guest lecture by George Theodorakopoulos on
trust in distributed systems and
- Recap of the distributed algorithm and analysis from
- Brief mention of additional topics such as network coding
- Summary of the main topics covered in the course.