Reliable Single Message Transmission and Graph Minors

 

Abstract

Reliable single message transmission considers the problem of sending a message from a sender s to a receiver r through an asynchronous, unreliable network, such as the Internet. In this talk, we consider the specific problem of transmitting a single message from s to r through a network in which edges may fail, but cannot recover. We assume that there is at least one s,r-path without failing edges, and our aim is to design a protocol that ensures that a message sent by s will be received by r (no matter which edges fail) without generating an infinite number of messages in the process.

We first give a structural characterization of graphs of networks that permit successful single message transmission. This leads to an explicit characterization of this family of networks in terms of forbidden rooted minors, which in turn leads to a linear time recognition algorithm. We also describe a protocol that ensures that the message is delivered if the network does not contain one of the forbidden minors.