Changelog Notes - Theory of Distributed Systems
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, it lacks some content that was 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)