Asymptotically optimal gossiping in radio networks

AbstractWe study the problem of gossiping in a system where n nodes are placed on a line of length Ln independently uniformly distributed. We assume that every node is equipped with a transmitter whose radius of transmission is 1. We further assume that simultaneous transmissions by neighboring nodes results in garbled messages.We present an algorithm for gossiping and show that it works in asymptotically optimal time. We assume that the system is synchronous and time is slotted and that nodes transmit only during a slot