NDLI: Fast message dissemination in random geometric networks

Please wait, while we are loading the content...

Fast message dissemination in random geometric networks

Content Provider	Springer Nature Link
Author	Czumaj, Artur Elsässer, Robert Gąsieniec, Leszek Sauerwald, Thomas Wang, Xin
Copyright Year	2011
Abstract	We analyze information dissemination in random geometric networks, which consist of n nodes placed uniformly at random in the square $${[0,\sqrt{n}]^{2}}$$ . In the corresponding graph two nodes u and v are connected by a (directed) edge, i.e., u is an (incoming) neighbor of v, if and only if the distance between u and v is smaller than the transmission radius assigned to u. In order to study the performance of distributed communication algorithms in such networks, we adopt here the ad-hoc radio communication model with no collision detection mechanism available. In this model the topology of network connections is not known in advance. Also a node v is capable of receiving a message from its neighbor u if u is the only (incoming) neighbor transmitting in a given step. Otherwise a collision occurs prompting interference that is not distinguishable from the background noise in the network. First, we consider networks modeled by random geometric graphs in which all nodes have the same radius $${r > \delta \sqrt{\log n}}$$ , where δ is a sufficiently large constant. In such networks, we provide a rigorous study of the classical communication problem of distributed gossiping (all-to-all communication). We examine various scenarios depending on initial local knowledge and capabilities of network nodes. We show that in many cases an asymptotically optimal distributed O(D)-time gossiping is feasible, where D stands for the diameter of the network. Later, we consider networks in which the transmission radii of the nodes vary according to a power law distribution, i.e., any node is assigned a transmission radius r > r min according to probability density function ρ(r) ~ r −α . More precisely, $${\rho(r) = (\alpha-1)r_{\min}^{\alpha-1} r^{-\alpha}}$$ , where $${\alpha \in (1, 3)}$$ and $${r_{\min} > \delta \sqrt{\log n}}$$ with δ being a large constant. In this case, we develop a simple broadcasting algorithm that runs in time O(log log n) (i.e., O(D)) always surely, and we show that this result is asymptotically optimal. Finally, we consider networks in which any node is assigned a transmission radius r > c according to the probability density function ρ(r) = (α−1)c α-1 r −α , where α is a constant from the same range as before and c is a constant. In this model the graph is usually not strongly connected, however, there is one giant component with Ω(n) nodes, and there is a directed path from each node of this giant component to every other node in the graph. We assume that the message which has to be disseminated is placed initially in one of the nodes of the giant component, and every node is aware of its own position in $${[0,\sqrt{n}] \times [0,\sqrt{n}]}$$ . Then, we show that there exists a randomized algorithm which delivers the broadcast message to all nodes in the network in time O(D . (log log n)2), almost always surely, where D stands for the diameter of the giant component of the graph. One can conclude from our studies that setting the transmission radii of the nodes according to a power law distribution brings clear advantages. In particular, one can design energy efficient radio networks with low average transmission radius, in which broadcasting can be performed exponentially faster than in the (extensively studied) case where all nodes have the uniform low transmission power.
Starting Page	1
Ending Page	24
Page Count	24
File Format	PDF
ISSN	01782770
Journal	Distributed Computing
Volume Number	26
Issue Number	1
e-ISSN	14320452
Language	English
Publisher	Springer-Verlag
Publisher Date	2011-12-21
Publisher Place	Berlin/Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Computer Communication Networks Computer Hardware Computer Systems Organization and Communication Networks Software Engineering/Programming and Operating Systems Theory of Computation
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computer Networks and Communications Computational Theory and Mathematics Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Fast and scalable rendezvousing

Fast computation by population protocols with a leader

Randomized leader election

The mailbox problem

Renaming in synchronous message passing systems with Byzantine failures

Byzantine agreement with homonyms

Election in partially anonymous networks with arbitrary knowledge in message passing systems

Coloring unstructured radio networks

Peer counting and sampling in overlay networks based on random walks

Fast message dissemination in random geometric networks

Similar Documents

Fast and scalable rendezvousing

Fast computation by population protocols with a leader

Randomized leader election

The mailbox problem

Renaming in synchronous message passing systems with Byzantine failures

Byzantine agreement with homonyms

Election in partially anonymous networks with arbitrary knowledge in message passing systems

Coloring unstructured radio networks

Peer counting and sampling in overlay networks based on random walks

Fast message dissemination in random geometric networks