Algorithms & Complexity

Group

Research

Teaching

Theses

back to main page

Logbook Theory of Distributed Systems - Winter 2021/22

• Lecture 25:
  Three generals problem for faulty nodes, Oral-Messages (OM) algorithm solves consensus for m traitors and n ≥ 3m+1 generals in time O(n^m), Proof-of-work consensus in bitcoin, aspects of bitcoin mining.

  Literature:
  • Notes: Sections 12.2, 12.3
  • n generals problem due to
    Lamport, Shostak, Pease. The Byzantine Generals Problem. ACM Trans. Programming Languages and Systems 4(3):382–401, 1982.
  • For a more detailed discussion of the OM algorithm see, e.g.,
    Kshemkalyani, Singhal. Consensus and agreement algorithms. Chapter 14 in: Distributed Computing - Principles, Algorithms, and Systems. Cambridge Univ. Press, 2012.



• Lecture 24:
  Blockchain and cryptocurrencies, trust in financial systems, basic design ideas of cryptocurrencies, double spending attack, consensus for consistent blockchain updates. Byzantine fault tolerance, consensus problem, two generals problem for faulty communication, three generals problem for faulty nodes, consensus (im)possibility for m traitors and more than (at most) 3m generals

  Literature:
  • Notes: Sections 12.1, 12.2
  • The problem underlying the two generals problem is discussed in
    Akkoyunlu, Ekanadham, Huber. Some Constraints and Tradeoffs in the Design of Network Communications. SOSP 1975
  • n generals problem due to
    Lamport, Shostak, Pease. The Byzantine Generals Problem. ACM Trans. Programming Languages and Systems 4(3):382–401, 1982.



• Lecture 23:
  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})

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



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

  Literature:
  • Notes: Sections 11.1, 11.2
  • Hoefer, Sauerwald. Threshold Load Balancing in Networks. PODC 2013 (BA).



• Lecture 21:
  Online learning in maximum independent set problems, independence number α(G), c-independent conflict graphs, no-regret learning yields an O(c)-approximation. Jamming, (T', 1-δ)-jammer, learning in phases, phase success when ν-fraction of successful rounds, histories that are γ-successful and η-blocking yield O(c/(γ η ν))-approximation, suitable choice of parameters for online learning gives O(c/δ)-approximation when T' and δ are known, or O(c/δ²)-approximation for jamming with unknown T'

  
  

  Note: The independence number α(G) was defined in the lecture video via bounded indegree for every node v_i from every independent set I. Instead, in the notes we use a definition via bounded outdegree of every node v_i to every independent set I, similar to the notion of c-independence. The defintions are equivalent in graphs with symmetric weights, and the relation α(G) ≥ ρ(G) stated in the video applies in these graphs.

  
  Literature:
  • Notes: Sections 10.4.2, 10.4.3
  • No-regret learning for the SINR model analyzed in
    Asgeirsson, Mitra. On a Game-theoretic Approach to Capacity Maximization in Wireless Networks. INFOCOM 2011.
  • Analysis framework for learning with jamming in
    Dams, Hoefer, Kesselheim. Jamming-Resistant Learning in Wireless Networks. IEEE/ACM Trans. Networking 24(5):2809-2818, 2016.



• Lecture 20:
  Minimal number of colors is chromatic number χ(G), inductive independence number ρ(G), χ(G) = Ω(MaxAvg(G)/ρ(G)), LogColor yields O(ρ(G) log n)-approximation for minimizing the number of colors. ρ(G) is O(1) or O(log n) in all prominent interference models. Online learning, application in maximum independent set problems, Exp3-WN algorithm

  Literature:
  • Notes: Sections 10.3, 10.4, 10.4.1
  • Expression of SINR model as directed, edge-weighted conflict graph is discussed in
    Hoefer, Kesselheim, Vöcking. Approximation Algorithms for Secondary Spectrum Auctions. ACM Trans. Internet Technology 14(2-3):16, 2014.
  • Algorithm LogColor is analyzed for the SINR model in
    Kesselheim, Vöcking. Distributed Contention Resolution in Wireless Networks. DISC 2010.
  • No-regret learning for the SINR model analyzed in
    Asgeirsson, Mitra. On a Game-theoretic Approach to Capacity Maximization in Wireless Networks. INFOCOM 2011.



• Lecture 19:
  Modeling interference, disk graph model, protocol model, SINR model, expression as edge-weighted, directed conflict graph G, set of conflict-free transmissions is independent set in G. Coloring, MaxAvg(G) is maximum average indegree of all induced subgraphs. Algorithm LogColor computes feasible coloring in O((1+MaxAvg(G)) log n) rounds whp

  Literature:
  • Notes: Sections 10.2, 10.3
  • Expression of SINR model as directed, edge-weighted conflict graph is discussed in
    Hoefer, Kesselheim, Vöcking. Approximation Algorithms for Secondary Spectrum Auctions. ACM Trans. Internet Technology 14(2-3):16, 2014.
  • Algorithm LogColor is analyzed for the SINR model in
    Kesselheim, Vöcking. Distributed Contention Resolution in Wireless Networks. DISC 2010.



• Lecture 18:
  Wireless networks, complete conflict graph, ALOHA protocol for leader election in expected O(1) time, initialization in expected time O(n): non-uniform (with knowledge of n), uniform (without knowledge of n) with collision detection, uniform and a given leader (but without collision detection). Uniform leader election in time O(log² n) w.h.p., uniform leader election with collision detection in time O(log n) w.h.p., improvement to time O(log log n) with probability 1 - O(log log n / log n)

  Remark: There was a mistake in the presentation of algorithm ULE-CD at minute 58. Instead of deleting the nodes transmitting, the nodes not transmitting are deleted in every round. This ensures that there is always one leader in the end.

  Literature:
  • Notes: Sections 10, 10.1, 10.1.1, 10.1.2
  • ALOHA protocol and the ALOHAnet:
    Abramson. THE ALOHA SYSTEM: Another alternative for computer communications. In Proc. Fall Joint Computer Conf. 1970.
    Binder, Abramson, Kuo, Okinaka, Wax. ALOHA packet broadcasting: A retrospect. In Amer. Fed. Inf. Proc. Soc. Nat. Comput. Conf. (AFIPS NCC), 1975.
    Abramson. Development of the ALOHANET. IEEE Trans. Inf. Theory, 31(2):119–123, 1985.
  • Tree-based algorithms for speeding up leader election based on ideas in
    Tsybakov, Mikhailov. Slotted multiaccess packet broadcasting feedback channel. Problemy Peredachi Informatsii, 14:32–59, 1978.
    Capetanakis. Tree algorithms for packet broadcast channels. IEEE Trans. Inf. Theory, 25(5):505–515, 1979.
    
  • Log-log-time leader election first achieved by
    Willard. Log-Logarithmic Selection Resolution Protocols in a Multiple Access Channel. SIAM J. Comput., 15(2):468–477, 1986.



• Lecture 17:
  Randomized oblivious routing in general networks, packet scheduling with GrowingRank protocol, for a set of shortest paths GrowingRank delivers N packets in time O(C + D + log N) whp.

  Literature:
  • Notes: Section 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 16:
  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

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



• Lecture 15:
  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

  Literature:
  • Notes: Sections 8.2, 8.2.1
  • 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 14:
  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

  Literature:
  • Notes: Sections 8, 8.1
  • Leighton book, Section 3.4.2
  • Lower bound for deterministic oblivious routing due to
    Borodin, Hopcroft. Routing, Merging, and Sorting on Parallel Models of Computation. J. Comput. Syst. Sci. 30(1):130-145, 1985.



• Lecture 13:
  APSP in unweighted graphs, APSP with relabeling on trees, 5-approximation with relabeling in time O(Diam(G) + $\sqrt{n\; log\; n}$),

  Literature:
  • Notes: Section 7.2
  • Analysis of 5-APSP algorithm due to
    Lenzen, Peleg. Efficient distributed source detection with limited bandwidth. PODC 2013.
    



• Lecture 12:
  APSP in unweighted graphs, PipeBF Algorithm, correctness and time complexity of n + O(Diam(G)) rounds, APSP in weighted graphs, (1+ε)-approximation in time O(n log n)
  
  In contrast to what I said in the video, i(v,w) = 0 is allowed, so we run PipeBF for all G_i for i=0,...,i_max. Although i=0 leaves all distances untouched, the PipeBF algorithm runs in time O(n), because it only computes the entries of L_0,v up to a distance in O(n). Hence, it might not return a distance for all pairs of nodes. For these pairs, higher values of i are required to capture the correct distance/hop trade-off.

  Literature:
  • Notes: Sections 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 11:
  Lower Bound of Ω($\sqrt{n}$ / log n) for time complexity of MST construction in graphs with diameter O(n^1/4), All-Pairs-Shortest-Path Problem, Lower Bound of Ω(n / log n) for time complexity of APSP in unweighted trees, Pipelined Bellman-Ford Algorithm

  Literature:
  • Notes: Sections 6.4, 7, 7.1
  • Peleg Book, Section 24.3, Chapter 9
  • 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.
    



• Lecture 10:
  Minimum Spanning Trees, Example Dual Greedy, 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 - 16.11.2021:
  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 - 11.11.2021:
  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 - 09.11.2021:
  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 - 04.11.2020:
  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 - 02.11.2020:
  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 - 28.10.2021:
  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 - 26.10.2021:
  Trees in the asynchronous CONGEST model: Pipelined convergecast for computing k semigroup functions in parallel, asymptotically optimal time complexity for synchronous and asynchronous cases, upcast of unordered items in time O(Depth(T) + m), Applications (route-disjoint matching, token distribution), 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, 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 - 21.10.2021:
  Flood for broadcast, Flood&Echo, message and time complexity in synchronous and asynchronous case, Converge(f,X) for computing semigroup functions

  Literature:
  • Notes: Sections 3, 3.1, 3.2, 3.3
  • Peleg Book: Sections 3.1, 3.3, 3.4



• Lecture 1 - 19.10.2021:
  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