A dynamic graph algorithm for the highly dynamic network problem

A recent flooding algorithm (R. O´Dell and R. Wattenhofer, 2005) guaranteed correctness for networks with dynamic edges and fixed nodes. The algorithm provided a partial answer to the highly dynamic network (HDN) problem, defined as the problem of devising a reliable message-passing algorithm over a HDN, which is a network - or a network mobility model - where edges and nodes can enter and leave the network almost arbitrarily. In this paper, we relax the flooding algorithms´ assumptions by removing the requirement that the network stays connected at all time, and extend the algorithm to solve the HDN problem where dynamic nodes are also involved. The extended algorithm is reliable: it guarantees message-passing to all the destination nodes and terminates within a time bounded by a polynomial function of the maximum message transit time between adjacent nodes, and the maximum number of nodes in the network