Achieving Efficiency, Robustness, and Security in Distributed Computing

dc.contributor.advisorPandurangan, Gopal
dc.contributor.committeeMemberVerma, Rakesh M.
dc.contributor.committeeMemberJohnsson, Lennart
dc.contributor.committeeMemberRobinson, Peter
dc.creatorChatterjee, Soumyottam 1987-
dc.creator.orcid0000-0002-0479-0690 2019 2019
dc.description.abstractThis 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 - n^{-c}$, 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(n\log^3{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 $\Omega(n)$ messages (even when $n$ is known), regardless of the number of rounds. We also present an $O(n\log{n})$ message deterministic algorithm that takes $O(\log{n})$ 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(\log^3{n}$) rounds) algorithm that guarantees that most nodes in the network (i.e., $\geq (1 - \epsilon)$-fraction of the nodes; for any small $\epsilon > 0$) will know a constant factor approximation of $\log{n}$. 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 $\frac{n}{\polylog{(n)}}$ number of Byzantine nodes and {\em continual heavy} churn of up to $\frac{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.
dc.description.departmentComputer Science, Department of
dc.format.digitalOriginborn digital
dc.identifier.citationPortions 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.
dc.rightsThe author of this work is the copyright owner. UH Libraries and the Texas Digital Library have their permission to store and provide access to this work. UH Libraries has secured permission to reproduce any and all previously published materials contained in the work. Further transmission, reproduction, or presentation of this work is prohibited except with permission of the author(s).
dc.subjectDistributed computing
dc.subjectLeader election
dc.subjectTime complexity
dc.subjectMessage complexity
dc.subjectByzantine counting
dc.subjectByzantine routing
dc.subjectDistributed hash table
dc.titleAchieving Efficiency, Robustness, and Security in Distributed Computing
local.embargo.terms2021-08-01 of Natural Sciences and Mathematics Science Science of Houston of Philosophy


Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
734.13 KB
Adobe Portable Document Format

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
4.44 KB
Plain Text
No Thumbnail Available
1.82 KB
Plain Text