Achieving Efficiency, Robustness, and Security in Distributed Computing



Journal Title

Journal ISSN

Volume Title



This dissertation investigates ways to improve various performance metrics of distributed computing systems. We begin with a study of the \emph{message complexity} of the \emph{leader election} problem in diameter-two networks. We first give a simple randomized Monte-Carlo leader election algorithm that with high probability\footnote{Throughout this dissertation, we would use eith high probability'' or whp'' to mean ``with probability at least 1−nc, where n is the network size (i.e., the number of nodes in the network) and c is some fixed positive constant.} succeeds and uses O(nlog3⁡n) messages and runs in O(1) rounds. We then show that any algorithm (even Monte Carlo randomized algorithms with large enough constant success probability) needs Ω(n) messages (even when n is known), regardless of the number of rounds. We also present an O(nlogn) message deterministic algorithm that takes O(logn) rounds (but needs knowledge of n); we show that this message complexity is tight for deterministic algorithms. Next we move on to designing algorithms that are provably robust to network malfunction and instability. First we consider the \emph{Byzantine counting} problem, that asks for an estimate of the network size n (i.e., the number of nodes in the network) in the presence of Byzantine or malicious nodes. We design a fast (running in O(log3⁡n) rounds) algorithm that guarantees that most nodes in the network (i.e., ≥(1−ϵ)-fraction of the nodes; for any small ϵ>0) will know a constant factor approximation of logn. Ours is the first fully local (decentralized and needing no global information) distributed algorithm that solves this important problem. Finally we design and analyze a randomized distributed protocol that guarantees with high probability the construction and maintenance of a sparse (where each node in the network has degree at most \polylog(n)) distributed hash table (DHT) network that guarantees efficient and reliable communication between (almost all pairs of) good nodes even in the presence of n\polylog(n) number of Byzantine nodes and {\em continual heavy} churn of up to n\polylog(n) {\em adversarially} chosen nodes joining and leaving every round (where n is the stable network size). To our knowledge, this is the first protocol that can guarantee the above properties under such a large number of Byzantine nodes in a highly dynamic setting.



Distributed computing, Leader election, Time complexity, Message complexity, Byzantine counting, Byzantine routing, Distributed hash table, DHT


Portions of this document appear in: Chatterjee, Soumyottam, Gopal Pandurangan, and Peter Robinson. "Network Size Estimation in Small-World Networks Under Byzantine Faults." In 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 855-865. IEEE, 2019. And in: Chatterjee, Soumyottam, Gopal Pandurangan, and Peter Robinson. "The complexity of leader election in diameter-two networks." Distributed Computing (2019): 1-17. And in: Chatterjee, Soumyottam, Gopal Pandurangan, and Peter Robinson. "The Complexity of Leader Election: A Chasm at Diameter Two." In Proceedings of the 19th International Conference on Distributed Computing and Networking, p. 13. ACM, 2018.