Message Efficient Fault-Tolerant Distributed Computations

Abstract

The thesis focuses on exploring the message complexity of some fundamental problems – leader election, agreement, and graph realization. Leader Election and Agreement problems are widely applicable in various domains such as sensor networks, IoT networks, grid computing, peer-to-peer networks, and cloud computing. Achieving low-cost and scalable leader election and agreement protocols with probabilistic guarantees is often desirable in large-scale distributed networks. Fur- thermore, the rise of permissionless distributed systems has made it necessary to design protocols that can tolerate an arbitrary number of faulty nodes. On the other hand, graph realization problems deal with constructing graphs that satisfy certain predefined properties (such as a degree sequence) in the presence of crashes. Despite intensive research, there has yet to be a practical solution to fault-tolerant problems for large-scale networks. One key reason for this is the large message complexity of currently known protocols. In this thesis, we focus on two main questions: (1) How efficiently leader election, agreement, and graph realization can be computed in a distributed network? (2) What can be the resilience of the network and how does it affect the complexity? In this thesis, we study four problems to address the above questions: (i) Leader election and agreement under crash fault (ii) Byzantine agreement (BA) (iii) Distributed graph realization, and (iv) Leader election in diameter-two networks. We present randomized (Monte Carlo) algorithms for leader election and agreement problems that achieve sublinear (in n, number of nodes) message complexity in the implicit version of the two problems when tolerating more than a constant frac- tion of the faulty nodes. Our algorithms tolerate any number of faulty nodes up to (n − polylog n) which is compensated by the increased complexity. The message complexity (and also the time complexity) of our algorithms is optimal (up to a polylog n factor). Further, we study the message complexity of authenticated Byzantine agreements under an honest majority. We focus on the “im- plicit” Byzantine agreement problem and show that a sublinear message complexity BA protocol under honest majority is possible in the standard PKI model when the nodes have access to an unbiased global coin and hash function. Our algorithm is optimal (up to a polylog n factor) and works in anonymous networks, where nodes do not know each other. We further study the graph realization problem in the Congested Clique model of distributed computing under crash faults. Our main result is a O(f )-round deterministic algorithm for the degree-sequence realization prob- lem in a n-node Congested Clique, of which f nodes could be faulty (f < n). The algorithm uses O(n2) messages. Our results are optimal in both the models with or without the knowledge of the neighbors (a.k.a. KT1 and KT0 model) w.r.t the number of rounds and the messages simultane- ously. Later, we investigate the leader election problem in diameter-two networks. We present a O(log n)-round deterministic leader election algorithm which incurs optimal O(n log n) messages without the knowledge of n.