PhD Dissertation Defense: Alex Weaver
Title: “Unknown Participants, Changing Topologies, and Faulty Devices: New Bounds for Distributed Algorithms in Challenging Wireless Network Models”
In this thesis we study several distributed problems in complex algorithm models designed to represent certain challenges associated with wireless networks. We begin by studying the contention resolution problem in a model we introduce in which the exact size of the network is unknown, but a probability distribution over the possible sizes is provided as input to the algorithm. We study this problem with and without collision detection, in both cases proving upper and lower bounds for the time complexity of the problem, revealing an interesting dependence on the Shannon entropy of the provided network size distribution.
We then turn our attention to the one-shot gossip and capacity problems. We study both of these problems the mobile telephone model (MTM), a recently introduced peer-to-peer model designed to capture the constraints and capabilities of wireless mesh networks created by existing smartphone communication technologies. We once again prove upper and lower bounds for the complexities of these problems. We then extend the MTM by introducing a new model which eliminates the assumption of synchronized rounds, proving an upper bound for the one-shot gossip problem in this harder asynchronous model.
Finally, we explore two classic graph structuring problems, the maximal independent set (MIS) and maximal matching (MM) problems, in variations of the well-studied broadcast-CONGEST model which allows for the possibility of different types of device failures. We first introduce model which includes crash failures. This model divides an algorithm execution into two stages. During the first stage, preparation for the crashes can be made. In the second stage, which begins after the crashes occur, the algorithm attempts to compute a valid structure with respect to the surviving subgraph. In this model we show upper and lower bounds for how quickly an MIS and MM can be repaired in the second stage, given some amount of precomputation performed in the first. We then introduce a model which allows for a bounded number of byzantine failures. In this model, we define what it means to correctly compute an MIS and provide upper and lower bounds on the time required to do so with respect to the number of failures.
Committee members:
Cal Newport (co-adviser)
Nitin Vaidya (co-adviser)
Bala Kalyanasundaram
Justin Thaler