NDLI: Brief announcement: minimum spanning trees and cone-based topology control

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

The life and times of a zookeeper

Preventing versus curing: avoiding conflicts in transactional memories

Tight bounds for clock synchronization

The weakest failure detector for solving k-set agreement

The forgiving graph: a distributed data structure for low stretch under adversarial attack

Fast distributed random walks

The wireless synchronization problem

Efficient broadcasting in known topology radio networks with long-range interference

Brief announcement: Stateless distributed algorithms for generalized packing linear programs

Brief announcement: a note on distributed stable matching

Brief announcement: the price of anonymity: optimal consensus despite asynchrony, crash and anonymity

Brief announcement: PUSH, a DISC shell

Brief announcement: the theory of network tracing

Brief announcement: hardness of broadcasting in wireless networks with unreliable communication

Refining the way to consensus

Cassandra: structured storage system on a P2P network

Dynamic atomic storage without consensus

Load balancing without regret in the bulletin board model

Simple and efficient asynchronous byzantine agreement with optimal resilience

A distributed polylogarithmic time algorithm for self-stabilizing skip graphs

Distributed and parallel algorithms for weighted vertex cover and other covering problems

SINR diagrams: towards algorithmically usable SINR models of wireless networks

The effect of power-law degrees on the navigability of small worlds: [extended abstract]

Brief announcement: concurrent non-commutative boosted transactions

On a selfish caching game

Brief announcement: minimum spanning trees and cone-based topology control

Brief announcement: deaf, dumb, and chatting robots

Brief announcement: (more) efficient pruning of ad-hoc wireless networks

Brief announcement: complexity analysis and algorithm design for pipeline configuration in distributed networks

Memory models: a case for rethinking parallel languages and hardware

Pregel: a system for large-scale graph processing - "ABSTRACT"

Randomized mutual exclusion in O(log N / log log N) RMRs

Concurrent imitation dynamics in congestion games

Partial synchrony based on set timeliness

The flip markov chain and a randomising P2P protocol

Return of the primal-dual: distributed metric facilitylocation

Coloring unstructured wireless multi-hop networks

Bounding the locality of distributed routing algorithms

Brief announcement: distributed phase synchronization of dynamic set of processes

Brief announcement: non-self-stabilizing and self-stabilizing gathering in networks of mobile agents--the notion of speed

Brief announcement: locality-based aggregate computation in wireless sensor networks

Brief announcement: global consistency can be easier than point-to-point communication

Brief announcement: self-assembly as graph grammar as distributed system

Brief announcement: exactly electing a unique leader is not harder than computing symmetric functions on anonymous quantum networks

Emerging challenges and opportunities in parallel computing: the cretaceous redux?

Max registers, counters, and monotone circuits

Extracting quorum failure detectors

Fast scalable deterministic consensus for crash failures

Correctness of gossip-based membership under message loss

Oblivious interference scheduling

Parsimonious flooding in dynamic graphs

Brief announcement: how to speed-up fault-tolerant clock generation in VLSI systems-on-chip via pipelining

The disagreement power of an adversary: extended abstract

Brief announcement: tight lower bounds for greedy routing in uniform small world rings

Vertical paxos and primary-backup replication

Distributed discovery of large near-cliques

Brief announcement: impossibility results for optimistic fair exchange with multiple autonomous arbiters

Brief announcement: perfectly secure message transmission in directed networks re-visited

Brief announcement: weakest failure detectors via an egg-laying simulation

Brief announcement: optimal self-stabilizing multi-token ring: a randomized solution

Brief announcement: topology knowledge affects probabilistic reliable communication

Brief announcement: lightweight key agreement and digital certificates for wireless sensor networks

Brief announcement: collaborative measurement of upload speeds in P2P systems

Brief announcement: virtual world consistency: a new condition for STM systems

Brief announcement: optimization based rate allocation for application layer multicast

Brief announcement: fast scalable Byzantine agreement in the full information model with a nonadaptive adversary

Brief announcement: a platform for experimenting with mobile algorithms in a laboratory

Brief announcement: distributed algorithms for approximating wireless network capacity

Brief announcement: new bounds for the controller problem

Brief announcement: minimum spanning trees and cone-based topology control

Content Provider	ACM Digital Library
Author	Cornejo, Alejandro Lynch, Nancy
Abstract	Consider a setting where nodes can vary their transmission power thereby changing the network topology, the goal of topology control is to reduce the transmission power while ensuring the communication graph remains connected. Wattenhofer et al. [6] introduced the distributed cone-based topology control algorithm with parameter α (CBTC(α)) and proved it correct if α ≤ 2π/3. Li et al. [4] proposed performing asymmetric edge removal or increasing α to 5π/6, and proved that when applied separately these minimizations preserve connectivity. Bahramgiri et al. [1] proved that when α ≤ 2π/3 it was possible to extend the algorithm to work in three dimensions and described a variation to preserve k-connectivity. We give a short self-contained proof that when α ≤ 2π/3 the minimum spanning tree is contained in the graph produced by CBTC(α). Its interesting to note that by comparison, other popular topology control algorithms are variations of the Gabriel Graph [5], the Relative Neighbor Graph [2] or the Delaunay Triangulation [3]; all of which are structures known to contain the minimum spanning tree. The proof is essentially an application of a lemma proved by Yao [7]. As a consequence of this proof we get as corollaries new short proofs of some of the main results of Wattenhofer et al. [6], Li et al. [4] and Bahramgiri et al. [1]. (1) When α ≤ 2π/3 the algorithm CBTC(α) preserves connectivity [6]. (2) The asymmetric edge removal operation preserves connectivity [4]. (3) The algorithm can be extended to three dimensions [1], and generally to n-dimensional space.
Starting Page	296
Ending Page	297
Page Count	2
File Format	PDF
ISBN	9781605583969
DOI	10.1145/1582716.1582774
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-08-10
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Topology control Minimum spanning trees
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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