NDLI: (Near) optimal resource-competitive broadcast with jamming

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

A distributed perspective on graph connectivity and cuts

On dynamic bin packing for resource allocation in the cloud

On computing maximal independent sets of hypergraphs in parallel

Brief announcement: few buffers, many hot spots, and no tree saturation (with high probability)

Provably good scheduling for parallel programs that use data structures through implicit batching

Scheduling selfish jobs on multidimensional parallel machines

A simple and practical linear-work parallel algorithm for connectivity

The PCL theorem: transactions cannot be parallel, consistent and live

Brief announcement: fairness-efficiency tradeoffs in tiered storage allocation

Automatic complexity analysis of explicitly parallel programs

A universal approach to data center network design

Simple dynamics for plurality consensus

Finding approximate partitions and splitters in external memory

Parallel peeling algorithms

On the online fault-tolerant server consolidation problem

Hierarchical graph partitioning

Brief announcement: queue delegation locking

Phase-concurrent hash tables for determinism

LP rounding and combinatorial algorithms for minimizing active and busy time

Executing dynamic data-graph computations deterministically using chromatic scheduling

Adaptive integration of hardware and software lock elision techniques

Brief announcement: deadline-aware scheduling of big-data processing jobs

Parallel streaming frequency-based aggregates

(Near) optimal resource-competitive broadcast with jamming

On characterizing the data movement complexity of computational DAGs for parallel execution

Balanced allocations and double hashing

Competitively scheduling tasks with intermediate parallelizability

Simple parallel and distributed algorithms for spectral graph sparsification

Brief announcement: fast dual ring queues

Scheduling shared continuous resources on many-cores

Ordering heuristics for parallel graph coloring

Transaction-friendly condition variables

Brief announcement: parallelization of asynchronous variational integrators forshared memory architectures

Ephemeral networks with random availability of links: diameter and connectivity

Tradeoffs between synchronization, communication, and computation in parallel linear algebra computations

Experimental analysis of space-bounded schedulers

Brief announcement: concurrent data structures for efficient streaming aggregation

A note on multiprocessor speed scaling with precedence constraints

Brief annoucement: a distributed minimum cut approximation scheme

Locality-based network creation games

Brief announcement: cache-oblivious scheduling of streaming pipelines

Brief announcement: amoebot -- a new model for programmable matter

Brief announcement: persistent unfairness arising from cache residency imbalance

Brief announcement: faster 3-periodic merging networks

(Near) optimal resource-competitive broadcast with jamming

Content Provider	ACM Digital Library
Author	King, Valerie Pettie, Seth Saia, Jared Gilbert, Seth Young, Maxwell Porat, Ely
Abstract	We consider the problem of broadcasting a message from a sender to n ≥ 1 receivers in a time-slotted, single-hop, wireless network with a single communication channel. Sending and listening dominate the energy usage of small wireless devices and this is abstracted as a unit cost per time slot. A jamming adversary exists who can disrupt the channel at unit cost per time slot, and aims to prevent the transmission of the message. Let T be the number of slots jammed by the adversary. Our goal is to design algorithms whose cost is resource-competitive, that is, whose per-device cost is a function, preferably o(T), of the adversary's cost. Devices must work with limited knowledge. The values n, T, and the adversary's jamming strategy are unknown. For 1-to-1 communication, we provide an algorithm with an expected cost of O(√Tln(1/ε) + ln (1/ε)), which succeeds with probability at least 1-ε for any tunable parameter ε>0. For 1-to-n broadcast, we provide a very different algorithm that succeeds with high probability and yields an expected cost per device of O(√T/n log $^{4}$ T + $log^{6}$ n). Therefore, the bigger the system, the better advantage achieved over the adversary! We complement our upper bounds with tight or nearly tight lower bounds. We prove that any 1-to-1 communication algorithm with constant probability of success has expected cost Ω (√T). For 1-to-n broadcast we show that some node has cost Ω(√T). Finally, we consider a more powerful adversary that can spoof messages from the receiver, rather than just jam the channel. We prove that any 1-to-1 communication algorithm in this model has expected cost Ω(Tφ-1), where φ = 1+√5 ∕ 2 is the golden ratio. This matches an earlier upper bound of King, Saia, and Young.
Starting Page	257
Ending Page	266
Page Count	10
File Format	PDF
ISBN	9781450328210
DOI	10.1145/2612669.2612679
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-06-23
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Wireless sensor networks Resource competitive Theory Attack resistance Distributed algorithms Jamming
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