Name
Abstract | ||
|---|---|---|
Finding a maximal independent set (MIS) is a classic problem in graph theory that has been widely study in the context of distributed algorithms. Standard distributed MIS solutions focus on time complexity. Here we focus on a novel attribute, fairness, where we consider an MIS algorithm fair if all nodes have similar probabilities of joining the set. In many contexts, fairness is important because a node's election to the MIS can have an impact on the resources it consumes. This paper addresses fairness by providing a provably fair and efficient distributed MIS algorithm for unrooted trees. The algorithm runs in O(logn) time and guarantees a correct MIS such that each node enters the set with probability at least 1/4 - ε, for arbitrarily small ε. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2484239.2484291 | PODC |
Keywords | Field | DocType |
classic problem,maximal independent set,mis algorithm,brief announcement,graph theory,novel attribute,mis algorithm fair,paper addresses fairness,mis solution,similar probability,time complexity,fair maximal independent set,symmetry breaking | Graph theory,Discrete mathematics,Symmetry breaking,Computer science,Theoretical computer science,Distributed algorithm,Time complexity,Maximal independent set,Distributed computing | Conference |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jeremy T. Fineman | 1 | 587 | 36.10 |
| Calvin C. Newport | 2 | 1264 | 95.49 |
| Tonghe Wang | 3 | 0 | 0.34 |