Deterministic Computations in Time-Varying Graphs: Broadcasting Under Unstructured Mobility
Most highly dynamic infrastructure-less networks have in common that the assumption of connectivity does not necessarily hold at a given instant. Still, communication routes can be available between any pair of nodes over time and space. These networks (variously called delay-tolerant, disruptive-tolerant, challenged) are naturally modeled as time-varying graphs (or evolving graphs), where the existence of an edge is a function of time. The existing theoretical research on these networks and graphs has focused on probabilistic assumptions and analysis. The few deterministic results have been restricted to the well structured mobility patterns described by the class of periodically-varying graphs.