Smoothed Analysis of Leader Election in Distributed Networks

We study smoothed analysis of the leader election (LE) problem in distributed networks. Smoothed analysis is a hybrid between worst-case analysis and average-case analysis. It takes a worst-case instance for the algorithm and perturbs the input by adding some random noise and analyzes the algorithm on this perturbed input. We consider smoothed analysis, in which the topology of the input graph G is randomly perturbed by adding random edges to G. The complexity of the algorithm is parameterized by a smoothing parameter 0 <= epsilon(n) <= 1 which controls the amount of random edges to be added to the input graph G per round, where epsilon is a small function of n, e.g., n(-4) (n is the number of nodes in the graph G). Informally, epsilon is the probability that a random edge can be added to a node per round. We analyze the time and message complexity of leader election in the above smoothing model. We present the following three results in synchronous CONGEST distributed model: (i) A simple randomized algorithm that elects a leader with high probability (With high probability (or w.h.p. in short) means with probability >= 1 - 1/n.) in O((log n)/epsilon) rounds and uses O(root n log(2.5) n) messages. Note that both the time and the message bounds are optimal (up to a polylog n factor). (ii) A time-improved randomized algorithm that elects a leader with high probability in O(log n/root epsilon) rounds, but uses O(m + n log n) messages, where m is the number of edges in the input graph G. (iii) A deterministic algorithm (except the randomized smoothing part) which solves leader election in O(log(2) n/root epsilon) rounds and incurs O(m+n root epsilon log(2) n) messages. Our work extends the study of smoothed analysis of distributed problems one step further, an open direction raised by [7].