Distributed Algorithms and Lower Bounds for Some Fundamental Problems

Abstract

This thesis studies some fundamental problems in distributed computing in different models from different aspects.

One of the most fundamental distributed problems is leader election. We revisit classical results on leader election and improve their results significantly. We consider leader election in clique networks, where n nodes are connected by point-to-point communication links. In synchronous clique under simultaneous wake-up model, we give new trade-off  between message complexity and time complexity. Also, we give Ω(nlog n) lower bound of messages for time-bounded algorithm, i.e., for algorithms with a time complexity that is a function of n. For any  randomized Las Vegas leader election, we show a Ω(n) lower bound of message complexity. For the synchronous clique under adversarial wake-up model, we prove that a 2-round randomized algorithm that succeeds with constant probability must send Ω(n^1.5) messages in expectation, and give a tight algorithm matching this bound. In asynchronous clique model, we give the first algorithm that achieves a trade off between messages and time under the assumption that some subset of nodes is awoken by the adversary.

Dynamic problems are natural in distributed computing. Also, matching is one of the most important topics in computer science. We consider the problem of computing a maximal matching with a distributed algorithm in the presence of batch-dynamic changes to the graph topology. We assume that a graph of n nodes is vertex-partitioned among k players that communicate via message passing. Our goal is to provide an efficient algorithm that quickly updates the matching even if an adversary determines batches of l edge insertions or deletions. Assuming a link bandwidth of O(β log n) bits per round, for a parameter β ≥1, we first show a lower bound of Ω( l log k/(βk²log n)) rounds for recomputing a matching assuming an oblivious adversary who is unaware of the initial (random) vertex partition as well as the current state of the players, and a stronger lower bound of Ω(l/(βk log n)) rounds against an adaptive adversary, who may choose any balanced (but not necessarily random) vertex partition initially and who knows the current state of the players. We also present a randomized algorithm that has an initialization time of O(⌈n/(βk)⌉log n) rounds, while achieving an update time that  is independent of n: In more detail, the update time is O(⌈l/βk⌉log (βk)) against an oblivious adversary, who must fix all updates in advance. If we consider the stronger adaptive adversary, the update time becomes O(⌈l/(√βk)⌉log βk) rounds.

Graph clustering is another important problem both in theory and practice. Particularly, graph clustering helps design algorithms, but it is challenging to transform corresponding centralized algorithms to distributed settings. Our goal is to explore the limits of distributed algorithms. We study the problem of exactly recovering all communities (clusters) in a graph generated from the Stochastic Block Model (SBM). We first give two centralized algorithms and carefully implement them in the Massively Parallel Computation (MPC) model.

Date of Award	28 Jun 2024
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Minming LI (Supervisor) & Peter ROBINSON (External Co-Supervisor)