Algorithmen & Komplexität

Arbeitsgruppe

Forschung

Lehre

Abschlussarbeiten

back to main page

Logbook Theory of Distributed Systems - Winter 2018/19

• 13.02.2019:
  Q&A session.

  
  

• 06.02.2019:
  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:
  • 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.
  
  

• 05.02.2019:
  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:
  • 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.
  
  

• 30.01.2019:
  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'

  Literature:
  • 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.
  
  

• 29.01.2019:
  LogColorAck for coloring with acknowledgements in link-based models with bidirectional communication, dual instance G', O((1+MaxAvg(G,G'))² log n)-approximation. Online learning, application in maximum independent set problems, Exp3-WN algorithm

  Literature:
  • Algorithm LogColorAck 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.
  
  

• 23.01.2019:
  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. Minimal number of colors is chromatic number χ(G), inductive independence number ρ(G), χ(G) = Ω(MaxAvg(G)/ρ(G)), LogColor yields O(ρ(G) log n)-approximation. ρ(G) is O(1) or O(log n) in all prominent interference models known to date.

  Literature:
  • 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.
  
  

• 22.01.2019:
  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:
  • 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.
  
  

• 16.01.2019:
  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)

  Literature:
  • 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.
  
  

• 19.12.2018:
  Bounds on 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:
  • Feige, Peleg, Raghavan, Upfal. Randomized broadcast in networks. Random Struct. Algorithms 1(4):447–460, 1990.
  
  

• 18.12.2018:
  Rumor Spreading, Push/Pull/Push-Pull protocols, with probability 1-o(1) Push protocol informs all nodes in the n-node clique within O(log n) rounds

  Literature:
  • Frieze, Grimmett. The shortest-path problem for graphs with random arc-lengths. Disc. Appl. Math. 10(1):57-77, 1985.
  • Pittel. On Probabilistic Analysis of a Coalesced Hashing Algorithm. Ann. Probab. 15(3):1180-1202, 1987.
  
  

• 12.12.2018:
  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. Rumor Spreading, Push/Pull/Push-Pull protocols

  Literature:
  • 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.
  
  

• 11.12.2018:
  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:
  • 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.
  
  

• 05.12.2018:
  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:
  • Leighton book, Section 3.4.4
  • Randomized oblivious routing with random intermediate targets due to
    Valiant, Brebner. Universal schemes for parallel communication. STOC 1981.
  
  

• 04.12.2018:
  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:
  • 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.
  
  

• 28.11.2018:
  Q&A session.

  
  

• 27.11.2018:
  APSP in unweighted graphs, 5-approximation with relabeling in time O(Diam(G) + $\sqrt{n\; log\; n}$), APSP in weighted graphs, (1+ε)-approximation in time O(n log n)

  Literature:
  • Analysis of PipeBF and 5-APSP algorithms due to
    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.
    
  
  

• 21.11.2018:
  APSP in unweighted graphs, PipeBF Algorithm, correctness and time complexity of n + O(Diam(G)) rounds, APSP with relabeling on trees, 5-approximation with relabeling in general unweighted graphs

  Literature:
  • Peleg Book, Chapter 9 contains background on so-called store-and-forward routing in terms of objectives and quality measures.
  • Analysis of PipeBF and 5-APSP algorithms due to
    Lenzen, Peleg. Efficient distributed source detection with limited bandwidth. PODC 2013.
    
  
  

• 20.11.2018:
  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:
  • 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.
    
  
  

• 14.11.2018:
  Minimum Spanning Trees, Example Dual Greedy, GKP algorithm in time O(Diam(G) + $\sqrt{n}$ log^*n)

  Literature:
  • 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.
  
  

• 13.11.2018:
  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:
  • 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.
  
  

• 07.11.2018:
  With probability 1/4 Random-MIS decides in a phase at least a third of the undecided edges, expected running time O(log n). Independent random variables, 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:
  • 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
  
  

• 06.11.2018:
  Lower bound Ω(log^* n) for MIS in paths and rings, Random-MIS algorithm, correct with probability 1, execution in phases, in expectation half of the undecided edges get decided in each phase. Probabilistic tools: Union bound, Linearity of Expectation, Markov Inequality.

  Literature:
  • Peleg Book, Section 8.2.
  • In Section 8.4, 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
  
  

• 31.10.2018:
  Linial's lower bound: Ω(log^* n) rounds for 3-coloring paths/rings, Maximal Independent Set, greedy MIS-Rank algorithm (Time(MIS-Rank) = O(n), Message(MIS-Rank) = Θ(|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:
  • Peleg Book, Sections 7.5, 8.1, 8.2
  • Linial's lower bound in the lecture was based on
    Laurinharju, Suomela. Linial's Lower Bound Made Easy. PODC 2014.
  
  

• 30.10.2018:
  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:
  • Peleg Book, Sections 7, 7.1, 7.2, 7.3
  
  

• 24.10.2018:
  Review of BFS trees in the asynchronous CONGEST model, 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)))

  Literature:
  • Peleg Book, Sections 5.3, 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.
  
  

• 23.10.2018:
  Trees in the asynchronous CONGEST model: 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:
  • Peleg Book, Sections 4.2, 4.2.3, 4.3.3, 4.3.4, 5.1, 5.2, 5.3
  
  

• 17.10.2018:
  CONGEST, LOCAL and ASYNC models, 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 in parallel, asymptotically optimal time complexity for synchronous and asynchronous cases

  Literature:
  • Peleg Book, Sections 2.2.6, 3.1, 3.3, 3.4
  
  

• 16.10.2018:
  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.

  Literature:
  • 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