CaltechAUTHORS
  A Caltech Library Service

A dynamic graph algorithm for the highly dynamic network problem

Soedarmadji, Edwin and McEliece, Robert J. (2006) A dynamic graph algorithm for the highly dynamic network problem. In: Fourth annual IEEE International Conference on Pervasive Computing and Communications Workshops. IEEE , Los Alamitos, CA, pp. 101-105. ISBN 0-7695-2520-2 . http://resolver.caltech.edu/CaltechAUTHORS:20110616-134644787

[img]
Preview
PDF - Published Version
See Usage Policy.

212Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20110616-134644787

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/PERCOMW.2006.5 DOIArticle
Additional Information:© 2006 IEEE. Issue Date: 13-17 March 2006. Date of Current Version: 27 March 2006.
Record Number:CaltechAUTHORS:20110616-134644787
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20110616-134644787
Official Citation:Soedarmadji, E.; McEliece, R.J.; , "A dynamic graph algorithm for the highly dynamic network problem," Pervasive Computing and Communications Workshops, 2006. PerCom Workshops 2006. Fourth Annual IEEE International Conference on , vol., no., pp.5 pp.-105, 13-17 March 2006 doi: 10.1109/PERCOMW.2006.5 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1598947&isnumber=33623
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:24036
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:17 Jun 2011 17:26
Last Modified:31 Jan 2019 22:12

Repository Staff Only: item control page