NDLI: Local approximation schemes for topology control

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

On the complexity of distributed graph coloring

When selfish meets evil: byzantine players in a virus inoculation game

Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling

Computing separable functions via gossip

Self-stabilizing byzantine agreement

Oracle size: a new measure of difficulty for communication tasks

Common2 extended to stacks and unbounded concurrency

How fast can a very robust read be?

An Ω (n log n) lower bound on the cost of mutual exclusion

Synchronizing without locks is inherently expensive

The art of multiprocessor programming

Quorum placement in networks: minimizing network congestion

Routing without regret: on convergence to nash equilibria of regret-minimizing algorithms in routing games

Sketching asynchronous streams over a sliding window

Peer counting and sampling in overlay networks: random walk methods

Irreducibility and additivity of set agreement-oriented failure detector classes

Object location using path separators

Single-scanner multi-writer snapshot implementations are fast!

Reliable broadcast in radio networks: the bounded collision case

Lower bound for scalable Byzantine Agreement

Transactional contention management as a non-clairvoyant scheduling problem

Century papers at the first quarter-century milestone

Distributed verification of minimum spanning trees

Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation

Adversarial queuing on the multiple-access channel

On the topologies formed by selfish peers

Optimally efficient multi-valued byzantine agreement

Optimal-stretch name-independent compact routing in doubling metrics

An O(1) RMRs leader election algorithm

Possibility and complexity of probabilistic reliable communication in directed networks

Stably computable predicates are semilinear

Towards a theory of transactional contention managers

Distributed social systems

EquiCast: scalable multicast with selfish users

Veracity radius: capturing the locality of distributed computations

Timeliness, failure-detectors, and consensus performance

Local approximation schemes for topology control

Life is not a state-machine: the long road from research to production

Local approximation schemes for topology control

Content Provider	ACM Digital Library
Author	Damian, Mirela Pandit, Saurav Pemmaraju, Sriram
Abstract	This paper presents a distributed algorithm for wireless ad-hoc networks that runs in polylogarithmic number of rounds in the size of the network and constructs a lightweight, linear size, (1+ε)-spanner for any given ε > 0. A wireless network is modeled by a d-dimensional α-quasi unit ball graph (α-UBG), which is a higher dimensional generalization of the standard unit disk graph (UDG) model. The d-dimensional α-UBG model goes beyond the unrealistic "flat world" assumption of UDGs and also takes into account transmission errors, fading signal strength, and physical obstructions. The main result in the paper is this: for any fixed ε > 0, 0 < α ≤ 1, and d ≥ 2 there is a distributed algorithm running in O(log n•log* n) communication rounds on an n-node, d-dimensional α-UBG G that computes a (1+ε)-spanner G' of G with maximum degree Δ(G') = O(1) and total weight w(G') = O(w(MST(G)). This result is motivated by the topology control problem in wireless ad-hoc networks and improves on existing topology control algorithms along several dimensions. The technical contributions of the paper include a new, sequential, greedy algorithm with relaxed edge ordering and lazy updating, and clustering techniques for filtering out unnecessary edges.
Starting Page	208
Ending Page	217
Page Count	10
File Format	PDF
ISBN	1595933840
DOI	10.1145/1146381.1146413
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2006-07-23
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Spanners Unit ball graphs Topology control Wireless ad-hoc networks
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

Distributed construction of bounded-degree low-interference spanners of low weight

On local algorithms for topology control and routing in ad hoc networks

Local Construction of Near-Optimal Power Spanners for Wireless Ad Hoc Networks

Local approximation schemes for ad hoc and sensor networks

Cooperative energy spanners: Energy-efficient topology control in cooperative ad hoc networks

Return of the primal-dual: distributed metric facilitylocation

TopCoF: A Topology Control Framework for Wireless Ad Hoc Networks

Geometric spanners for wireless ad hoc networks

Local, distributed topology control for large-scale wireless ad-hoc networks

Local approximation schemes for topology control

Similar Documents

Distributed construction of bounded-degree low-interference spanners of low weight

On local algorithms for topology control and routing in ad hoc networks

Local Construction of Near-Optimal Power Spanners for Wireless Ad Hoc Networks

Local approximation schemes for ad hoc and sensor networks

Cooperative energy spanners: Energy-efficient topology control in cooperative ad hoc networks

Return of the primal-dual: distributed metric facilitylocation

TopCoF: A Topology Control Framework for Wireless Ad Hoc Networks

Geometric spanners for wireless ad hoc networks

Local, distributed topology control for large-scale wireless ad-hoc networks

Local approximation schemes for topology control