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
dc.date.accessioned2019-11-08T02:59:30Z
dc.date.createdAugust 2019
dc.date.issued2019-08
dc.date.submittedAugust 2019
dc.date.updated2019-11-08T02:59:30Z
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.format.mimetypeapplication/pdf
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.identifier.urihttps://hdl.handle.net/10657/5337
dc.language.isoeng
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.subjectDHT
dc.titleAchieving Efficiency, Robustness, and Security in Distributed Computing
dc.type.dcmiText
dc.type.genreThesis
local.embargo.lift2021-08-01
local.embargo.terms2021-08-01
thesis.degree.collegeCollege of Natural Sciences and Mathematics
thesis.degree.departmentComputer Science
thesis.degree.disciplineComputer Science
thesis.degree.grantorUniversity of Houston
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
CHATTERJEE-DISSERTATION-2019.pdf
Size:
734.13 KB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.44 KB
Format:
Plain Text
Description:
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.82 KB
Format:
Plain Text
Description: