A dynamic graph algorithm for the highly dynamic network problem
- Creators
- Soedarmadji, Edwin
- McEliece, Robert J.
Abstract
A recent flooding algorithm [1] 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.
Additional Information
© 2006 IEEE. Issue Date: 13-17 March 2006. Date of Current Version: 27 March 2006.Attached Files
Files
Name | Size | Download all |
---|---|---|
md5:f8a57df3c3c202513f3d0eb24d9b1148
|
217.2 kB | Preview Download |
Additional details
- Eprint ID
- 24036
- Resolver ID
- CaltechAUTHORS:20110616-134644787
- Created
-
2011-06-17Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field