NDLI: Scaling Bounds for Function Computation over Large Networks

Content Provider	IEEE Xplore Digital Library
Author	Subramanian, S. Gupta, P. Shakkottai, S.
Copyright Year	2007
Description	Author affiliation: Dept. of Electr. & Comput. Eng., Univ. of Texas at Austin, Austin, TX (Subramanian, S.)
Abstract	We develop order bounds on the refresh rate of computing functions over large multi-hop sensor networks, with finite degree (finite neighbors for each node). The refresh rate quantifies how often the function can be re-computed with new data at sensor nodes. Giridhar and Kumar (2005) considered deterministic function computation for two important classes of functions (type-threshold and type-sensitive functions) and showed that for networks with high degree (random planar geometric graph with n nodes and average degree Theta(log n)), type- threshold functions (e.g. max) are easy to compute (refresh rate of Theta(1/log(n))), and type-sensitive functions (e.g. average) can be computed only at a rate Theta(1/log(n)). In this paper, we first show that type-threshold functions can be computed at an optimal refresh rate of Theta(1) over networks with finite degree. However, the computation of type-sensitive function do not become uniformly faster as the graph degree becomes smaller. We demonstrate that while some type-sensitive functions (such as computing parity) are not hard to compute in finite degree graphs (we can achieve a refresh rate proportional to (1/d), where d is the maximum graph degree), there exist type-sensitive functions (e.g., computing the average to one-bit precision) in this class that cannot be deterministically computed faster than Theta(1/log n) even for finite degree graphs. However, by relaxing the requirements to allow probabilistic guarantees, computing the average can be achieved at a refresh rate of Theta(1) over any graph with bounded degree and a refresh rate of Theta(1/ log log n) for random planar networks. Further, for random planar networks operating over an AWGN channel with signal power path-loss, we show that even refresh rates of Theta(1) can be achieved with vanishing distortion when the power path- loss exponent is strictly less than 4. Thus, relaxing deterministic computation guarantees to probabilistic requirements enables sizea
Starting Page	136
Ending Page	140
File Size	444866
Page Count	5
File Format	PDF
ISBN	9781424413973
DOI	10.1109/ISIT.2007.4557216
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2007-06-24
Publisher Place	France
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Computer networks Tree graphs Power control Spread spectrum communication AWGN channels Distortion Upper bound Interference constraints Distributed computing Lattices
Content Type	Text
Resource Type	Article

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

On the scaling of interference alignment under delay and power constraints

Capacity and power control in spread spectrum macrodiversity radio networks

Performance bounds of non-uniform signaling over AWGN channels

Power optimal routing in wireless networks

Error Probability Bounds and Approximations for DS Spread-Spectrum Communication Systems with Mutiple Tone or Multiple Access Interference

Computation over Gaussian Multiple-Access Channels

Capacity scaling of cognitive networks: Beyond interference-limited communication

Capacity Scaling of Wireless Networks With Inhomogeneous Node Density: Lower Bounds

Performance bounds for direct-sequence spread-spectrum communications with complex signature sequences

Scaling Bounds for Function Computation over Large Networks

Similar Documents

On the scaling of interference alignment under delay and power constraints

Capacity and power control in spread spectrum macrodiversity radio networks

Performance bounds of non-uniform signaling over AWGN channels

Power optimal routing in wireless networks

Error Probability Bounds and Approximations for DS Spread-Spectrum Communication Systems with Mutiple Tone or Multiple Access Interference

Computation over Gaussian Multiple-Access Channels

Capacity scaling of cognitive networks: Beyond interference-limited communication

Capacity Scaling of Wireless Networks With Inhomogeneous Node Density: Lower Bounds

Performance bounds for direct-sequence spread-spectrum communications with complex signature sequences

Scaling Bounds for Function Computation over Large Networks