Czumaj, Artur and Wang, Xin (2007) Fast message dissemination in random geometric ad-hoc radio networks. In: 18th International Symposium on Algorithms and Computations (ISAAC 2007), Sendai, JAPAN, DEC 17-19, 2007. Published in: ALGORITHMS AND COMPUTATION, 4835 pp. 220-231.

Full text not available from this repository.

Abstract

We study the complexity of distributed protocols for the classical information dissemination problem of distributed gossiping. We consider the model of random geometric networks, one of the main models used to study properties of sensor and ad-hoc networks, where n points are randomly placed in a unit square and two points are connected by an edge/link if they are at at most a certain fixed distance r from each other. To study communication in the network, we consider the ad-hoc radio networks model of communication. We examine various scenarios depending on the local knowledge of each node in the networks, and show that in many settings distributed gossiping in asymptotically optimal time O(D) is possible, where D is the diameter of the network and thus a trivial lower bound for any communication.

Item Type:	Conference Item (UNSPECIFIED)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Series Name:	LECTURE NOTES IN COMPUTER SCIENCE
Journal or Publication Title:	ALGORITHMS AND COMPUTATION
Publisher:	SPRINGER-VERLAG BERLIN
ISBN:	978-3-540-77118-0
ISSN:	0302-9743
Editor:	Tokuyama, T
Date:	2007
Volume:	4835
Number of Pages:	12
Page Range:	pp. 220-231
Publication Status:	Published
Title of Event:	18th International Symposium on Algorithms and Computations (ISAAC 2007)
Location of Event:	Sendai, JAPAN
Date(s) of Event:	DEC 17-19, 2007
URI:	http://wrap.warwick.ac.uk/id/eprint/30642

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item