Dissertation Defense: Tonghe Wang
Candidate Name: Tonghe Wang
Major: Computer Science
Advisor: Calvin Newport, Ph.D.
Title: Fairness for Distributed Algorithms
In this thesis, we explore a new but intuitive notion of “fairness” that focuses on the equality of outcomes of distributed algorithms. In particular, this thesis will study new definitions of fairness with respect to four general topics: graph algorithms, communication algorithms, contention resolution algorithms, and consensus algorithms.
First, we explore fair graph algorithms by tackling with two different problems: maximal independent set and vertex coloring. We propose a novel definition of fairness that applies to each problem and study new upper and lower bounds with respect to this metric.
We then turn our attention to communication algorithms that consider the quality of the communication links. We explore the possibility of competitive rate selection algorithms that guarantee throughput within reasonable factors of the optimal achievable rate at each receiver. We argue that a competitive rate selection strategy is fair to every receiver with respect to the capacity of its link to the sender.
We then consider the classical contention resolution problem. In this thesis, we propose the definition of the fairness of contention resolution algorithms with both multiple channels and collision detection. We also describe and analyze fair contention resolution algorithms that match, or come within a logloglog n factor of matching, a recently proved lower bound in the same setting for all relevant parameters. Of equal importance, our solutions introduce a novel new technique in which we leverage a distributed structure we call coalescing cohorts to simulate a well-known parallel search strategy from the structured PRAM CREW model in our unstructured distributed model.
Finally, we turn our attention to the asynchronous shared memory model and study the new concept of fair consensus. A fair consensus algorithm, intuitively, guarantees every proposed value is decided with similar probability. Defining and achieving this property is more complex.We will also explore the conjecture that the use of fair consensus algorithms will simplify the implementations of replicated state machines and provide stronger fairness properties to the applications that leverage these machines for consistency.
Thursday, July 20 at 10:00am to 12:00pm
St. Mary's Hall, 326
3700 Reservoir Road, N.W., Washington