NDLI: Towards Power-Sensitive Communication on a Multiple-Access Channel

Content Provider	IEEE Xplore Digital Library
Author	Marco, G.D. Kowalski, D.R.
Copyright Year	2010
Abstract	We are given $n$ stations of which $k$ are active, while the remaining $n-k$ are asleep. The active stations communicate via a multiple-access channel. If a subset $Q$ of active stations transmits in the same round, all active stations can recognize from the signal strength how many stations have transmitted (i.e., they learn the size of set $Q$), even though they may not be able to decode the contents of transmitted messages. The goal is to let each active station to learn about the set of all active stations. It is well known that $\Theta(k\log_{k+1} n)$ rounds are enough, even for non-adaptive deterministic algorithms. A natural interesting generalization arises when we are required to identify a subset of $m\leq k$ active stations. We show that while for randomized or for adaptive deterministic algorithms $O(m \log_{m+1} n)$ rounds are sufficient, the non-adaptive deterministic counterpart still requires $\Theta(k\log_{k+1} n)$ rounds, therefore, finding any subset of active stations is not easier than finding all of them by a non-adaptive deterministic algorithm. We prove our results in the more general framework of combinatorial search theory, where the problem of identifying active stations on a multiple-access channel can be viewed as a variant of the well-known counterfeit coin problem.
Starting Page	728
Ending Page	735
File Size	356753
Page Count	8
File Format	PDF
ISBN	9781424472611
ISSN	10636927
e-ISBN	9781424472628
DOI	10.1109/ICDCS.2010.50
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-06-21
Publisher Place	Italy
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Counterfeiting Feedback Springs Adaptive algorithm Testing Distributed computing Decoding Councils Algorithm design and analysis combinatorial search theory multiple-access channel distributed learning randomized algorithms
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Software

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

Two new quorum based algorithms for distributed mutual exclusion

Randomized mutual exclusion on a multiple access channel

Explicit Combinatorial Structures for Cooperative Distributed Algorithms

Channel Adaptive Encoding and Decoding Strategies and Rate Regions for the Three User Cooperative Multiple Access Channel

Achievable rates for the three user cooperative multiple access channel

A Distributed Termination Detection Algorithm for Dynamic Asynchronous Systems

Fast Collect in the absence of contention

Distributed Adaptive Algorithms for Optimal Opportunistic Medium Access

Distributed Node Coloring in the SINR Model

Towards Power-Sensitive Communication on a Multiple-Access Channel

Similar Documents

Two new quorum based algorithms for distributed mutual exclusion

Randomized mutual exclusion on a multiple access channel

Explicit Combinatorial Structures for Cooperative Distributed Algorithms

Channel Adaptive Encoding and Decoding Strategies and Rate Regions for the Three User Cooperative Multiple Access Channel

Achievable rates for the three user cooperative multiple access channel

A Distributed Termination Detection Algorithm for Dynamic Asynchronous Systems

Fast Collect in the absence of contention

Distributed Adaptive Algorithms for Optimal Opportunistic Medium Access

Distributed Node Coloring in the SINR Model

Towards Power-Sensitive Communication on a Multiple-Access Channel