# Achieving Efficiency, Robustness, and Security in Distributed Computing

dc.contributor.advisor | Pandurangan, Gopal | |

dc.contributor.committeeMember | Verma, Rakesh M. | |

dc.contributor.committeeMember | Johnsson, Lennart | |

dc.contributor.committeeMember | Robinson, Peter | |

dc.creator | Chatterjee, Soumyottam 1987- | |

dc.creator.orcid | 0000-0002-0479-0690 | |

dc.date.accessioned | 2019-11-08T02:59:30Z | |

dc.date.created | August 2019 | |

dc.date.issued | 2019-08 | |

dc.date.submitted | August 2019 | |

dc.date.updated | 2019-11-08T02:59:30Z | |

dc.description.abstract | 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 - 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.department | Computer Science, Department of | |

dc.format.digitalOrigin | born digital | |

dc.format.mimetype | application/pdf | |

dc.identifier.citation | 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. | |

dc.identifier.uri | https://hdl.handle.net/10657/5337 | |

dc.language.iso | eng | |

dc.rights | The 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.subject | Distributed computing | |

dc.subject | Leader election | |

dc.subject | Time complexity | |

dc.subject | Message complexity | |

dc.subject | Byzantine counting | |

dc.subject | Byzantine routing | |

dc.subject | Distributed hash table | |

dc.subject | DHT | |

dc.title | Achieving Efficiency, Robustness, and Security in Distributed Computing | |

dc.type.dcmi | Text | |

dc.type.genre | Thesis | |

local.embargo.lift | 2021-08-01 | |

local.embargo.terms | 2021-08-01 | |

thesis.degree.college | College of Natural Sciences and Mathematics | |

thesis.degree.department | Computer Science | |

thesis.degree.discipline | Computer Science | |

thesis.degree.grantor | University of Houston | |

thesis.degree.level | Doctoral | |

thesis.degree.name | Doctor of Philosophy |

## Files

### Original bundle

1 - 1 of 1

Loading...

- Name:
- CHATTERJEE-DISSERTATION-2019.pdf
- Size:
- 734.13 KB
- Format:
- Adobe Portable Document Format