Asynchronous leader election and MIS using abstract MAC layer
Nancy Ann Lynch, Tsvetomira Radeva, Srikanth Sastry · 2012
We study leader election (LE) and computation of a maximal independent set (MIS) in wireless ad-hoc networks. We use the abstract MAC layer proposed in [14] to divorce the algorithmic complexity of solving these problems from the low-level issues of contention and collisions. We demonstrate the advantages of such a MAC layer by presenting simple asynchronous deterministic algorithms to solve LE and MIS and proving their correctness. First, we present an LE algorithm for static single-hop networks in which each process sends no more than three messages to its neighbors in the system. Next, we present an algorithm to compute an MIS in a static multi-hop network in which each process sends a constant number of messages to each of its neighbors in the communication graph.