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
computation, etc.
Lecture 1, 8/31:
- Scope of class, focus on distributed algorithms and probabilistic
techniques;
- 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
protocols etc.;
- 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,
and applications.
Lecture 2, 9/2:
- 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 3, 9/7:
- Why the expectation being small enough or large enough may not always
suffice;
- 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
higher moments;
- A glimpse of neighborhoods and interference in multihop wireless
networks, scheduling using Luby's vertex-coloring protocol
[Lu93], analysis.
Lecture 4, 9/9:
- 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 5, 9/14:
- 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 6, 9/16:
- 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.
Lecture 7, 9/21:
- 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
vertex-connectivity;
- Begin [LMR94] distributed packet-routing.
The next several lectures mainly cover distributed algorithms,
P2P systems, and overlay networks.
Lecture 8, 9/23:
- 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
[BL+03].
Lecture 9, 9/28:
- Complete almost all of main analysis of
[BL+03], and
discussion of associated useful probabilistic techniques.
Lecture 10, 9/30:
- Complete
[BL+03];
- Routers and input-queued switches, brief discussion of switch-scheduling
framework of
[AM+03];
- Start algorithm of
[PS97], in a switch-scheduling and resource-allocation context.
Lecture 11, 10/05:
- Complete part of the analysis of
[PS97], by proving tail bounds for sums of negatively correlated random
variables.
- Introduction to Martingales, Martingale tail bounds, allusion to
[Dub98].
- Start Chord from [SM+03].
Lecture 12, 10/07:
Guest Lecture by Prof. Bobby Bhattacharjee.
- Covered search in replication in P2P systems, including
[GB+04] and
[G2-04].
Lecture 13, 10/12:
- Continue discussion of Chord from [SM+03]: properties of the distribution
of peers on Chord ring, lookup time, behavior under node-additions,
stabilization.
- Start [KS04].
Lecture 14, 10/14:
Lecture 15, 10/19:
- 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.
10/21: Mid-term, no lecture.
Lecture 16, 10/26:
- P2P networks that are sensitive to network-distance: start
[PRR99];
- Brief allusion to extensions of
[PRR99], including the main result of
[HKK04].
Lecture 17, 10/28:
- Further intuition and search algorithm of
[PRR99];
- Unstructured P2P networks, the natural random-walk approach of
[GMS04], and relevant background on Markov Chains and random walks from
[GMS04].
The next several lectures mainly cover wireless, ad hoc and
sensor networks.
Lecture 18, 11/02:
- 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;
- Start
[KDG03]: the basic setup, and Uniform Gossip.
Lecture 19, 11/04:
- 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 20, 11/09:
- 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
trees;
- 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 21, 11/11:
- 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
[Raj02]);
- Degenerate/inductive graphs and inductive coloring; how Luby's algorithm
[Lu93] extends to such colorings;
- Review of ALOHA/Ethernet protocol and introduction to
stochastic domination.
Lecture 22, 11/16:
- 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 23, 11/18:
- Complete the discussion of disk-graph scheduling
from [KM+04];
- Cover the "cone-coverage" algorithm for topology control, due to
[WL+01];
- A very brief introduction to information theory and coding theory:
basic definitions and the capacity of the binary symmetric channel.
Lecture 24, 11/23:
Guest Lecture by Srinivasan Parthasarathy:
- 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
source-destination pairs.
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
distributed algorithms.
Lecture 25, 11/30:
- Start
[Adl02]: background, the models considered, and full analysis of the case
"b = 1" for a single path of attack.
Lecture 26, 12/02:
Continue
[Adl02]:
- 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 27, 12/07:
- Recap of basic ideas behind the protocol of
[Adl02] for general k;
- Network decomposition: applications and the distributed algorithm
of [LS93].
Lecture 28, 12/09:
- Brief guest lecture by George Theodorakopoulos on
trust in distributed systems and
[TB04];
- Recap of the distributed algorithm and analysis from
[LS93];
- Brief mention of additional topics such as network coding
(see, e.g.,
[AC+00] and
[NEC]);
- Summary of the main topics covered in the course.