Algorithms & Complexity

Computer Science 1

Group

Research

Teaching

Misc

back to main page

Logbook Theory of Distributed Systems - Summer 2025

• Lecture 16 - 03.06.2025:
  Random walks, basic definitions, load balancing with random walks, expected time to balanced distribution is O(H(G) log Φ(ℓ⁰)), where H(G) is the hitting time of G and ℓ⁰ is the initial number of active units

  Literature:
  • Notes: Section 9.2
  • Hoefer, Sauerwald. Threshold Load Balancing in Networks. PODC 2013 (BA).



• Lecture 15 - 02.06.2025:
  GrowingRank protocol, proof of delivery time O(C + D + log N) whp. Rumor Spreading, Push protocol, time T after which the Push protocol with probability 1-1/n has informed all nodes, in general T = O(n log n) and T = Ω(log n), Degree-Diameter bound: T = O(Δ max{Diam(G), log n})
  
  The bound of O(d²ℓ) stated in the notes is correct - for O(d² ℓ log ℓ) stated in the lecture, degree and diameter got mixed up :)

  Literature:
  • Notes: Sections 9.1, 9.1.1
  • Feige, Peleg, Raghavan, Upfal. Randomized broadcast in networks. Random Struct. Algorithms 1(4):447–460, 1990.



• Lecture 14 - 27.05.2025:
  Randomized oblivious routing on the hypercube, packet scheduling with RandomRank protocol, for a set of bit-fixing paths RandomRank delivers all packets in time O(C + log n) whp. GrowingRank protocol for general networks, for a set of shortest paths GrowingRank delivers N packets in time O(C + D + log N) whp.

  Literature:
  • Notes: Sections 8.2.2, 8.2.3
  • Leighton book, Section 3.4.4
  • RandomRank and its generalization have their origins in the following papers:
    Alelinuas. Randomized Parallel Communication. PODC 1982.
    Upfal. Efficient Schemes for Parallel Communication. PODC 1982.



• Lecture 13 - 26.05.2025:
  Randomized oblivious routing on the hypercube, congestion C and dilation D, path selection with random intermediate targets gives a collection of paths with congestion of O(log n / log log n) whp. Packet scheduling using RandomRank protocol, short overview of the main result.

  Literature:
  • Notes: Sections 8.2, 8.2.1, 8.2.2
  • Leighton book, Section 3.4.4
  • Randomized oblivious routing with random intermediate targets due to
    Valiant, Brebner. Universal schemes for parallel communication. STOC 1981.



• Lecture 12 - 20.05.2025:
  APSP in weighted graphs, (1+ε)-approximation in time O(n log n). Store-and-forward packet routing, path selection, packet scheduling, permutation routing, mesh networks M(l,d), dimension-by-dimension routing in M(l,d). Deterministic oblivious routing, lower bound Ω($\sqrt{n}$/Δ) for every connected network and every path system (without proof). Definition randomized oblivious routing.

  Literature:
  • Notes: Sections 7.3, 8, 8.1, 8.2
  • Peleg Book, Chapter 9 contains background on store-and-forward routing in terms of objectives and quality measures.
  • Rounding tricks similar to one presented for weighted APSP are used often.
    The result in the lecture is due to
    Nanongkai. Distributed approximation algorithms for weighted shortest paths. STOC 2014.
    
  • Leighton book, Section 3.4.2
  • Lower bound for deterministic oblivious routing is presented in
    Borodin, Hopcroft. Routing, Merging, and Sorting on Parallel Models of Computation. J. Comput. Syst. Sci. 30(1):130-145, 1985.



• Lecture 11 - 19.05.2025:
  All-Pairs-Shortest-Path Problem, Lower Bound of Ω(n / log n) for time complexity of APSP in unweighted trees, Pipelined Bellman-Ford Algorithm, correctness and time complexity of n + O(Diam(G)) rounds, APSP in weighted graphs, rounding idea.

  Literature:
  • Notes: 7, 7.1, 7.3
  • Peleg Book, Chapter 9 contains background on so-called store-and-forward routing in terms of objectives and quality measures.
  • The PipeBF algorithm for APSP presented in the lecture was studied in
    Lenzen, Peleg. Efficient distributed source detection with limited bandwidth. PODC 2013.
    
  • Rounding tricks similar to one presented for weighted graphs are used often.
    The result in the lecture is due to
    Nanongkai. Distributed approximation algorithms for weighted shortest paths. STOC 2014.
    



• Lecture 10 - 13.05.2025:
  Minimum Spanning Trees, GKP algorithm in time O(Diam(G) + $\sqrt{n}$ log^*n)

  Literature:
  • Notes: Section 6.3
  • Peleg Book, Sections 5.6.3, 5.6.4, 24.2.
  • In Section 5.6, Dual Greedy is applied for the distributed solution of set optimization problems with matroid structure, which generalizes MST. This comes in handy, since in the GKP algorithm we use Dual Greedy over the entire graph for finding only the edges of an inter-component MST.
  • In Section 24.2, a slightly different symmetry breaking mechanism based on dominating sets (instead of tree coloring and maximal matching) is used to guarantee small-diameter components in the GKP algorithm.



• Lecture 9 - 12.05.2025:
  Minimum Spanning Trees, characterization with blue and red edges, centralized Kruskal algorithm, distributed GHS algorithm in time O(n log n), distributed Dual Greedy algorithm in time O(n).

  Literature:
  • Notes: Sections 6, 6.1, 6.2
  • Peleg Book, Sections 5.5, 5.5.2 5.6.2, 5.6.3, 5.6.4.
  • In Section 5.6, Dual Greedy is applied for the distributed solution of general set optimization problems with so-called matroid structure.
  • The improvement of the GHS algorithm to time O(n) and message complexity O(|E| + n log n) is due to
    Awerbuch. Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems. STOC 1987.



• Lecture 8 - 05.05.2025:
  Review expected running time of Random-MIS, Chernoff bounds, definition "with high probability" (whp). Random-MIS needs O(log n) rounds whp, bit complexity, Random-MIS needs only O(log n)-bit messages in all rounds whp. Applications of MIS for solving (Δ+1)-coloring, maximal matching, vertex cover. Probabilistic tools: Markov Inequality, Chernoff Bounds.

  Literature:
  • Notes: Section 5.2.2
  • Random-MIS and the analysis in the lecture are due to
    Métivier, Robson, Saheb-Djahromi, Zemmari. An optimal bit complexity randomized distributed MIS algorithm. Distributed Computing 23(5-6):331-340, 2011.
  • Background for Probability Tools: Markov Inequality, Chernoff Bounds



• Lecture 7 - 29.04.2025:
  Random-MIS algorithm, correct with probability 1, execution in phases, in each phase in expectation half of the undecided edges get decided, in each phase with probability at least 1/4 at least a third of the undecided edges get decided, expected running time O(log n). Probabilistic tools: Union bound, Linearity of Expectation, Markov Inequality.

  Literature:
  • Notes: Section 5.2.2
  • In Section 8.4 of Peleg's book, a different randomized algorithm for MIS is analyzed. The bound on the expected running time is only O(log² n).
  • Random-MIS and the analysis in the lecture are due to
    Métivier, Robson, Saheb-Djahromi, Zemmari. An optimal bit complexity randomized distributed MIS algorithm. Distributed Computing 23(5-6):331-340, 2011.
  • Background for Probability Tools: Linearity of Expectation, Union Bound, Markov Inequality



• Lecture 6 - 28.04.2025:
  Linial's lower bound: Ω(log^* n) rounds for 3-coloring paths/rings, Maximal Independent Set, greedy MIS-Rank algorithm (Time: O(n), Message: Θ(|E|)), Color2MIS obtains MIS from coloring, combined with coloring algorithms gives MIS in trees and bounded-degree graphs in time O(log^* n), lower bound Ω(log^* n) for MIS in paths and rings: Obtain 3-coloring from MIS and apply Linial's lower bound

  Literature:
  • Notes: Sections 5.1.2, 5.2, 5.2.1
  • Peleg Book, Sections 7.5, 8.1, 8.2
  • Linial's lower bound in the lecture based on
    Laurinharju, Suomela. Linial's Lower Bound Made Easy. PODC 2014.



• 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