Changelog Notes - Theory of Distributed Systems
June 16:
- Section 9.1: The Degree-Diamater bound extends directly to the Pull protocol. Added bounds for the Pull protocol in complete and star graphs in Theorem 26.
- Section 10.1: Fixed typos and broken references.
June 3:
- Merged Chapters 9 and 11 into one chapter on "Randomized Processes", now the new Chapter 9. Previous Chapter 9 is now Section 9.1 on Rumor Spreading, we removed some parts that were not covered in the lectures. Previous Chapter 11 is now Section 9.2 on Random Walks (including all previous content).
May 13:
- Section 5.2.3, Theorem 13: A time complexity of O(T(G)) for the coloring algorithm holds only if Δ is constant. The statement of the theorem was changed and restricted to the application of the randomized MIS algorithm. This was previously the statement of Corollary 5 (which is omitted now).
April 29:
- Section 5.2: In the first attempt, the probability that rv is maximal in the neighborhood of v is 1/(deg(v) + 1) (not deg(v)).
- Proof of Lemma 25: The size of the set Γ'(v,w) is at most deg(v)+deg(w). Consequently, the probability of event (v → w) is at least 1/(deg(v) + deg(w)).
April 14:
- Section 3.3: Convergecast of sums of m-bit numbers has message complexity O(nm/log n) and time complexity O(Depth(T) m / log n)