The first several lectures cover probabilistic preliminaries, and applications in distributed algorithms, wireless networks, data-stream computation, etc.

- 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.

- 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.

- 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.

- 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.

- 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.

- 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 vertex-connectivity;
- Begin [LMR94] distributed packet-routing.

The next several lectures mainly cover distributed algorithms, P2P systems, and overlay networks.

- 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].

- Complete almost all of main analysis of [BL+03], and discussion of associated useful probabilistic techniques.

- 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.

- 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].

- 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].

- Complete [KS04].

- 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.

- P2P networks that are sensitive to network-distance: start [PRR99];
- Brief allusion to extensions of [PRR99], including the main result of [HKK04].

- 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,

- 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.

- 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.

- 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.

- 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.

- 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.

- 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.

- 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

- Start [Adl02]: background, the models considered, and full analysis of the case "b = 1" for a single path of attack.

- 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.

- Recap of basic ideas behind the protocol of [Adl02] for general k;
- Network decomposition: applications and the distributed algorithm of [LS93].

- 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.