NDLI: Sleeping on the job: energy-efficient and robust broadcast for 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

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

Content Provider	ACM Digital Library
Author	King, Valerie Saia, Jared Young, Maxwell Phillips, Cynthia
Abstract	We address the problem of minimizing power consumption when broadcasting a message from one node to all the other nodes in a radio network. To enable power savings for such a problem, we introduce a compelling new data streaming problem that we call the Bad Santa problem. Our results on this problem apply for any situation where: 1) a node can listen to a set of n nodes, out of which at least half are non-faulty and know the correct message; and 2) each of these n nodes sends according to some predetermined schedule which assigns each of them its own unique time slot. In this situation, we show that in order to receive the correct message with probability 1, it is necessary and sufficient for the listening node to listen to a Θ(√n) expected number of time slots. Moreover, if we allow for repetitions of transmissions so that each sending node sends the message O(log* n) times (i.e. in O(log* n) rounds each consisting of the n time slots), then listening to O(log* n) expected number of time slots suffices. We show that this is near optimal. We describe an application of our result to the popular grid model for a radio network. Each node in the network is located on a point in a two dimensional grid, and whenever a node sends a message, all awake nodes within $L_{∞}$ distance r receive the message. In this model, up to t< r/2 (2r+1) nodes within any 2r+1 by 2r+1 square in the grid can suffer Byzantine faults. Moreover, we assume that the nodes that suffer Byzantine faults are chosen and controlled by an adaptive adversary that knows everything except for the random bits of each non-faulty node. This type of adaptive adversary models worst-case behavior due to malicious attacks on the network; mobile nodes moving around in the network; or static nodes losing power or ceasing to function. Let n=r(2r+1). We show how to solve the broadcast problem in this model with each node awake only an expected O(1/√n) fraction of the time. Moreover, if we allow each node to send O(log* n) times, we can increase the energy savings so that each node is awake only an expected O((log* n)/ n) fraction of the time. This compares favorably with previous protocols that required each node to be awake for every time step.
Starting Page	243
Ending Page	252
Page Count	10
File Format	PDF
ISBN	9781595939890
DOI	10.1145/1400751.1400784
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-08-18
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Fault tolerance Broadcast Power aware Byzantine failure Radio networks Data streaming Energy efficient
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