Brief Announcement: Waiting in Dynamic Networks

Download Now Date Added: May 2012
Format: PDF

The authors consider infrastructure-less highly dynamic networks, where connectivity does not necessarily hold, and the network may actually be disconnected at every time instant. These networks are naturally modeled as time-varying graphs. Clearly the task of designing protocols for these networks is less difficult if the environment allows waiting (i.e., it provides the nodes with store-carry forward-like mechanisms such as local buffering) than if waiting is not feasible. They provide a quantitative corroboration of this fact in terms of the expressivity of the corresponding time-varying graph; that is in terms of the language generated by the feasible journeys in the graph.