Dissertation Defense - University of Houston

# Dissertation Defense

In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy

### Soumyottam Chatterjee

will defend his dissertation

## Achieving Efficiency, Robustness, and Security in Distributed Computing

Abstract

This thesis investigates ways to improve various performance metrics of distributed computing systems. The very first problem that we consider in the thesis is leader election, one of the most fundamental problems in distributed computing. We study the message complexity of the leader election problem in diameter-two networks and show matching upper and lower bounds for the same. Next we move on to designing algorithms that are provably robust to network malfunction and instability. First we consider the 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 a protocol that builds a routable structure that is provably secure and robust to the presence of a large number of Byzantine nodes as well as to heavy network churn (where a large number of nodes leave and join the network in every round). Ours is the first known work to achieve this particular goal that is an important first step forward in achieving secure, robust, efficient computation in dynamic networks, e.g., peer-to-peer networks.

Date: Wednesday, July 17, 2019
Time: 10:00 AM - 11:00 AM
Place: PGH 550