Theory of Distributed Systems - Summer 25

Logbook Theory of Distributed Systems - Summer 2025

Lecture 5 - 22.04.2025:
Vertex coloring in the synchronous LOCAL model, Reduce algorithm to (Δ+1)-color any graph with maximum degree Δ in time O(n), 6-Color algorithm to 6-color trees in time O(log^* n), refinement Six2Three to 3 colors in constant time, 2-coloring trees can require Ω(n) time, extension of 6-Color and Reduce to (Δ+1)-color arbitrary graphs with constant Δ
Literature:
- Notes: Sections 5, 5.1, 5.1.1
- Peleg Book, Sections 7, 7.1, 7.2, 7.3

Lecture 4 - 15.04.2025:
Synchronizers via pulse generation, pulse compatibility, correctness, readiness and delay rules, two- or three-phase implementation approach using safety and readiness information, examples: Synchronizer α (Message_pulse(α): O(|E|), Time_pulse(α): O(1)), synchronizer β (Message_pulse(β): O(n), Time_pulse(β): O(Diam(G))), and hybrid synchronizer γ based on clusters C with BFS trees T_C (Message_pulse(γ): O(|E_C| + n), Time_pulse(γ): O(max_C Depth(T_C)), where E_C is the set of intercluster edges)
Literature:
- Notes: Section 4.2
- Peleg Book, Sections 6.1, 6.2, 6.3 (for α and β), 25.1. (for γ)
- All three synchronizers are due to
  Awerbuch. Complexity of Network Synchronization. J. ACM 32(4):804-823, 1985.

Lecture 3 - 14.04.2025:
Upcast of unordered items in time O(Depth(T) + m), Applications (route-disjoint matching, token distribution). Asynchronous BFS-tree construction using Dijkstra (Time: O(Diam(G)²), Message: O(|E| + n Diam(G)), Bellman-Ford (Time: O(Diam(G)), Message: O(n|E|))
Literature:
- Notes: Sections 3.4.1, 4.1
- Peleg Book, Sections 4.2, 4.2.3, 4.3.3, 4.3.4, 5.1, 5.2, 5.3

Lecture 2 -- 08.04.2025:
Flood for broadcast, Flood&Echo, message and time complexity in synchronous and asynchronous case, Converge(f,X) for computing semigroup functions, pipelined convergecast for computing k semigroup functions
Literature:
- Notes: Sections 3, 3.1, 3.2, 3.3, 3.4
- Peleg Book: Sections 3.1, 3.3, 3.4

Lecture 1 -- 07.04.2025:
Introductory remarks, what do we mean by a distributed system?, basic modeling assumptions, graph-based message-passing model based on ports, basic graph-theoretic notions, synchronous and asynchronous variants of message passing, execution of distributed algorithms as event-driven state manipulation, definition of time and message complexity for synchronous and asynchronous models, CONGEST, LOCAL and ASYNC models.
Literature:
- Notes: Sections 1 and 2
- Peleg Book: Sections 1.1, 1.2, 1.3, 2.1.1, 2.1.2, 2.1.3, 2.2.1, 2.2.3, 2.2.4, 2.2.5, 2.2.6