NDLI: On selection problem in radio networks

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

A topological characterization of weakness

Distance estimation and object location via rings of neighbors

On the locality of bounded growth

The price of selfish behavior in bilateral network formation

Faster communication in known topology radio networks

Fast fault-tolerant agreement algorithms

Routing complexity of faulty networks

Advanced contention management for dynamic software transactional memory

Adaptive routing with stale information

Correctness of a gossip based membership protocol

Simultaneous broadcast revisited

Proof labeling schemes

Building scalable and robust peer-to-peer overlay networks for broadcasting using network coding

Skip-webs: efficient distributed data structures for multi-dimensional data sets

Facility location: distributed approximation

On reliable broadcast in a radio network

The combined power of conditions and failure detectors to solve asynchronous set agreement

Feedback control for router congestion resolution

Efficient multi-word locking using randomization

A network pricing game for selfish traffic

A scheme for load balancing in heterogenous distributed hash tables

Feasibility and complexity of broadcasting with random transmission failures

Efficient dependency tracking for relevant events in shared-memory systems

Efficient lookup on unstructured topologies

Primal-dual based distributed algorithms for vertex cover with semi-hard capacities

Maximal independent sets in radio networks

The weakest failure detector to solve nonuniform consensus

Competitive weighted throughput analysis of greedy protocols on DAGs

Toward a theory of transactional contention managers

On the establishment of distinct identities in overlay networks

Reliable broadcast in unknown fixed-identity networks

Policy-hiding access control in open environment

Quorum placement in networks to minimize access delays

Brief announcement: on the expected overpayment of VCG mechanisms in large networks

On selection problem in radio networks

Consensus and collision detectors in wireless Ad Hoc networks

Brief announcement: continuous containment and local stabilization in path-vector routing

Stochastic analysis of distributed deadlock scheduling

Brief announcement: controlled quorum selection in arbitrary topologies

Brief announcement: dynamic interoperable point-to-point connection of MPI implementations

Brief announcement: a flexible framework for secret handshakes

Brief announcement: ring-like DHTs and the postage stamp problem

Brief announcement: an incentive-compatible capacity assignment algorithm for bulk data distribution using P2P

Brief announcement: broadcast in radio networks in the presence of byzantine adversaries

Brief announcement: minimal system conditions to implement unreliable failure detectors

Brief announcement: gradient clock synchronization in sensor networks

Brief announcement: analysis of a randomized contention-resolution protocol for distributed access

Brief announcement: coupling for Markov decision processes - application to self-stabilization with arbitrary schedulers

Brief announcement: wait-free implementation of multiple-writers/multiple-readers atomic byzantine data storage systems

Brief announcement: strong detection of misconfigurations

Brief announcement: the overlay network content distribution problem

Brief announcement: distributed algorithmic mechanism design for scheduling

Brief announcement: exploring the consistency problem space

Brief announcement: on the possibility and the impossibility of message-driven self-stabilizing failure detection

Brief announcement: evaluation of tree-based data gathering algorithms for wireless sensor networks

Brief announcement: improved asynchronous group mutual exclusion in token-passing networks

Brief announcement: virtual stationary automata for mobile networks

Brief announcement: abstractions for implementing atomic objects in dynamic systems

On selection problem in radio networks

Content Provider	ACM Digital Library
Author	Kowalski, Dariusz R.
Abstract	A selection problem is among the basic communication primitives in networks. In this problem at most k participating stations have to broadcast successfully their messages. This problem is especially important in packet radio networks, where simultaneous transmissions of many neighbors result in interference among delivered messages. This work focuses on a single-hop radio networks with n-stations, also called a multiple access channel, and considers both static and dynamic versions of the selection problem. We construct a family of efficient oblivious deterministic protocols based on selectors, one of them with selection time cO(klog(n/k)), and the second explicit construction with selection time cO(k polylog n). The first construction matches the lower bound Ω(klog(n/k)) on deterministic oblivious selection, while the second one is the first known explicit construction better than $Θ(k^{2}).$ In the dynamic case we introduce the model of dynamic requests, called k-streams, which generalizes the static model and the dynamic requests with at most k participants. We prove that each oblivious deterministic protocol has latency $Ω(k^{2}/log$ k), and on the other hand we prove the existence of the oblivious deterministic protocol with latency $cO(k^{2}log$ n). In view of the existence of the randomized oblivious protocol with expected latency cO(klog(n/k)), this shows that randomization is substantially better than determinism for dynamic setting. Selection problem can be applied to implement other communication primitives --- we demonstrate it in the example of broadcast problem in multi-hop ad-hoc radio networks. In particular, we design an adaptive deterministic protocol broadcasting in time cO(nlog D) in every D-hop radio network of n-stations.
Starting Page	158
Ending Page	166
Page Count	9
File Format	PDF
ISBN	1581139942
DOI	10.1145/1073814.1073843
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-07-17
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Selection problem Broadcast problem Multiple access channel Radio networks
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