Randomized initialization protocols for packet radio networks

The main contribution of this work is to propose efficient randomized leader election and initialization protocols for Packet Radio Networks (PRN, for short). As a result of the initialization protocol, the n stations of a PRN are assigned distinct integer IDs from 1 to n. The results include protocols to: (1) initialize the single-channel PRN with the collision detection (CD) capability in O(n) rounds with probability at least 1-1/(2ⁿ); (2) initialize the k-channel PRN with CD capability in O(n/k) rounds with probability at least 1-1/n, whenever k⩽n/3 log n; (3) elect a leader on the single-channel PRN with no CD in O((log n)²) broadcast rounds with probability at least 1-1/n; (4) initialize the single-channel PRN with no CD in O(n) rounds with probability at least 1-1/(2√n); (5) initialize the k-channel PRN with no CD in O(n/k) broadcast rounds with probability at least 1-1/n, whenever k⩽n/(4(log n)²)