NDLI: On the effect of the deployment setting on broadcasting in Euclidean radio networks

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

Distributed computation of the mode

Anti-Ω: the weakest failure detector for set agreement

Collaborative enforcement of firewall policies in virtual private networks

On the complexity of asynchronous gossip

On a capacitated multivehicle routing problem

Flooding time in edge-Markovian dynamic graphs

Distributed algorithms for ultrasparse spanners and linear size skeletons

New combinatorial topology upper and lower bounds for renaming

Packet mode and QoS algorithms for buffered crossbar switches with FIFO queuing

Asynchronous exclusive selection

Forget him and keep on moving

BMobi_Causal: a causal broadcast protocol in mobile dynamic groups

A fast distributed slicing algorithm

A tradeoff analysis on message complexity and lifetime optimality for a distributed multicast algorithm in WSNs

Greedy distributed optimization of unsplittable multicommodity flows

Quantum distributed consensus

Optimizing consistency checking for memory-intensive transactions

The lotus-eater attack

Evolution of distributed computing theory: from concurrency to networks and beyond

Beyond nash equilibrium: solution concepts for the 21st century

Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition

Failure detectors in loosely named systems

Secure communication over radio channels

Brahms: byzantine resilient random membership sampling

Improved compact routing schemes for dynamic trees

On the effect of the deployment setting on broadcasting in Euclidean radio networks

Efficient distributed approximation algorithms via probabilistic tree embeddings

Timeliness-based wait-freedom: a gracefully degrading progress condition

The impact of randomization in smoothing networks

Fast self-stabilizing byzantine tolerant digital clock synchronization

Online and dynamic embeddings of approximate ultrametrics

Correctness criteria for replicated database systems with snapshot isolation replicas

A dynamic exchange game

Nearest-neighbor graphs on random point sets and their applications to sensor networks

Stateless distributed algorithms for near optimal maximum multicommodity flows

Looking for the optimal conditions for solving set agreement

Wait-free programming for general purpose computations on graphics processors

Extracting models from design documents with mapster

A world of (Im) possibilities

The internet is flat: a brief history of networking in the next ten years

A log-star distributed maximal independent set algorithm for growth-bounded graphs

Every problem has a weakest failure detector

On tradeoff between network connectivity, phase complexity and communication complexity of reliable communication tolerating mixed adversary

Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems

Tight bounds for delay-sensitive aggregation

Virtual infrastructure for collision-prone wireless networks

On the locality of distributed sparse spanner construction

Lower bounds for randomized consensus under a weak adversary

Optimizing data popularity conscious bloom filters

OCD: obsessive consensus disorder (or repetitive consensus)

Dynamic routing and location services in metrics of low doubling dimension

The asynchronous bounded-cycle model

Anonymous and censorship resistant content sharing in unstructured overlays

From anarchy to geometric structuring: the power of virtual coordinates

Distributed averaging in the presence of a sparse cut

Tight RMR lower bounds for mutual exclusion and other problems

Transactional memory retry mechanisms

Efficient single phase unconditionally secure message transmission with optimum communication complexity

The power of simulation relations

Accountability for distributed systems

A jamming-resistant MAC protocol for single-hop wireless networks

Sharing is harder than agreeing

CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory

Bounded budget connection (BBC) games or how to make friends and influence people, on a budget

The forgiving tree: a self-healing distributed data structure

Sleeping on the job: energy-efficient and robust broadcast for radio networks

The stretched exponential distribution of internet media access patterns

Randomized consensus in expected O(n log n) individual work

Distributed order scheduling and its application to multi-core dram controllers

An almost-surely terminating polynomial protocol for asynchronous byzantine agreement with optimal resilience

On ad hoc routing with guaranteed delivery

Model checking transactional memory with spin

Our brothers' keepers

Balancing energy consumption for uniform data gathering wireless sensor networks

Gossip-based aggregate computation: computing faster with non address-oblivious schemes

Closing the complexity gap between mutual exclusion and FCFS mutual exclusion

Scheduling tasks with dependencies on asymmetric multiprocessors

Mobile proactive secret sharing

On fault tolerance and wireless networks

On the internet delay space dimensionality

On the robustness of (semi) fast quorum-based implementations of atomic shared memory

Distributed churn measurement in arbitrary networks

Scheduling sensors by tilinglattices

Snap-stabilization in message-passing systems

Fault-tolerant implementations of atomic registers by safe registers in networks

The future of distributed computing: renaissance or reformation?

Maximizing quorum availability in multi-clustered systems

Principles of untrusted storage: a new look at consistency conditions

Efficient pipeline configuration in distributed heterogeneous computing environments

Power management of devices: when should i switch off?

Dynamic service assignment in mobile networks: the magma approach

Optimal failure detection with low sporadic overhead and communication locality

On the effect of the deployment setting on broadcasting in Euclidean radio networks

Content Provider	ACM Digital Library
Author	Kantor, Erez Emek, Yuval Peleg, David
Abstract	The paper studies broadcasting in radio networks whose stations are represented by points in the Euclidean plane. In any given time step, a station can either receive or transmit. A message transmitted from station (v) is delivered to every station (u) at distance at most (1) from (v), but (u) successfully hears the message if and only if (v) is the only station at distance at most (1) from (u) that transmitted in this time step. A designated source station has a message that should be disseminated throughout the network. All stations other than the source are initially idle and wake up upon the first time they hear the source message. It is shown in [11] that the time complexity of broadcasting depends on two parameters of the network, namely, its diameter (in hops) (D) and a lower bound (d) on the Euclidean distance between any two stations. The inverse of (d) is called the granularity of the network, denoted by (g). Specifically, the authors of [11] present a broadcasting algorithm that works in time (O (D g)) and prove that every broadcasting algorithm requires Ω (D √g) time. In this paper, we distinguish between the arbitrary deployment setting, originally studied in [11], in which stations can be placed everywhere in the plane, and the new grid deployment setting, in which stations are only allowed to be placed on a (d)-spaced grid. Does the latter (more restricted) setting provides any speedup in broadcasting time complexity? Although the (O (D g)) broadcasting algorithm of [11] works under the (original) arbitrary deployment setting, it turns out that the Ω (D √g) lower bound remains valid under the grid deployment setting. Still, the above question is left unanswered. The current paper answers this question affirmatively by presenting a provable separation between the two deployment settings. We establish a tight lower bound on the time complexity of broadcasting under the arbitrary deployment setting proving that broadcasting cannot be completed in less than Ω ( D √g) time. For the grid deployment setting, we develop a broadcasting algorithm that runs in time O ( D g5 / 6 log g), thus breaking the linear dependency on (g).
Starting Page	223
Ending Page	232
Page Count	10
File Format	PDF
ISBN	9781595939890
DOI	10.1145/1400751.1400782
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-08-18
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Broadcasting Ad hoc networks Radio networks Unit disk graphs
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