| Title | : | Efficient and Practical Leader Election |
| Speaker | : | Pappu Kumar (IITM) |
| Details | : | Fri, 24 Oct, 2025 3:30 PM @ SSB 334 |
| Abstract: | : | Leader election (LE) is one of the most fundamental and well-studied problems in distributed computing, with applications ranging from classical to modern systems. The obvious lower bounds on time and message complexity for explicit leader election are $Omega$(1) and $Omega$(n) on complete networks, and $Omega$(n) and $Omega$(n) on ring networks, respectively, where n is the number of nodes in the network. A long line of research has aimed at achieving bounds that are tight with respect to these lower bounds. In search of theoretically interesting results, the algorithms proposed in the past tend to be complex, hard to implement, and often hide large constants under asymptotic notation (e.g., big O), making them impractical in most scenarios. In this paper, we propose significantly simpler and easier-to-implement randomized leader election algorithms for asynchronous complete networks and asynchronous ring networks. We prove correctness for all our proposed algorithms. To study their performances, we simulated our algorithms along with several key algorithms from the literature using the NS-3 simulator, and conducted systematic performance comparison on large networks of about a million nodes. Our algorithms achieve less time and messages in our experiments than established LE algorithms. web conference link https://meet.google.com/yee-azeo-ujf |
