Fairness for Distributed Algorithm

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 studies 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. This new definition of fairness requires, roughly speaking, that each node has a similar probability of ending up with each possible outcome. We then turn our attention to communication algorithms that consider the quality of the communication links. We explore new upper and lower bounds for fair rate selection algorithms that guarantee throughput within reasonable factors of the optimal achievable rate at each receiver. We study both single hop and multihop networks, as well as links with static quality and those with qualities that can change over time.;We then consider new fair solutions to the classical contention resolution problem, where we define "fairness" in this context to mean each process has a similar probability of being the process that first breaks symmetry.We focus in particular on the setting with multiple channels and collision detection (for which little results were known until recently). We describe and analyze a new fair contention resolution algorithm that comes within small factors of matching a recently proved lower bound of this setting. 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 describe and analyze a new consensus algorithm that satisfies our new definition of fairness. We also show how to implement a replicated state machine that applies a fair consensus algorithm as subroutine.