We study asynchronous packet radio networks in which transmissions among nodes may be delayed. We consider the task of broadcasting a message generated by the source node. The timing of arrivals of messages is controlled by adversaries. We consider three different adversaries. The edge adversary can have a transmitted message delivered at different times to different recipients. The crash adversary is the edge one augmented by the ability to crash nodes. The node adversary can have a message received at arbitrary times, but simultaneously by all the recipients. A protocol specifies for each node how many times the message is retransmitted by this node, after it has been received. The total number of transmissions of nodes is defined to be a measure of performance of a broadcast protocol, and is called its work. The radio network is modeled as a graph and is given as input to a centralized algorithm. An aim of the algorithm could be either to find a broadcast protocol, possibly with additional properties, or to verify correctness of a given protocol. We give an algorithm to find a protocol correct against the edge adversary. The obtained protocol is work-exponential in general. This is an inherent property of the problem, as is justified by a lower bound. We develop a polynomial algorithm to verify correctness of a given protocol for a given network against the edge adversary. We show that a problem to decide if there exists a protocol, for a given network and of a specified work performance, is NP-hard. We extend some of these results to the remaining two adversaries.
展开▼
