Monitoring Churn in Wireless Networks
Wireless networks often experience a significant amount of churn, i.e. the arrival and departure of nodes, and often it is necessary to keep all nodes informed about all other nodes in the network. In this paper, the authors propose a distributed algorithm for single-hop networks that detects churn, meaning that the nodes observe other nodes joining or leaving the network and inform all other nodes in the network about their observations. Their algorithm works correctly even if the nodes which join or leave and the respective points in time are chosen by an adversary in a worst-case fashion. The delay until notification is small, such that all nodes of the network are informed about changes quickly, in asymptotically optimal time.