On λ-Alert Problem

Marek Klonowski 1 Dominik Pajak 2, 3
3 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : In this paper we introduce and analyse the λ-Alert problem: in a single hop radio network a subset of stations is activated. The aim of the protocol is to decide if the number of activated stations is greater or equal to λ. This problem is similar to the k-Selection problem. It can also be seen as an extension of the standard Alert problem. In our paper we consider the λ-Alert problem in various settings. We describe characteristics of oblivious and adaptive deterministic algorithms for the model with and without collision detection. We also show some results for randomized algorithms. In particular, we present a very efficient Las Vegas- type algorithm which is immune to an adversary.
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-00996841
Contributor : Dominik Pajak <>
Submitted on : Tuesday, May 27, 2014 - 9:30:09 AM
Last modification on : Thursday, January 11, 2018 - 6:22:12 AM
Long-term archiving on : Wednesday, August 27, 2014 - 11:01:03 AM

File

ipdps.pdf
Files produced by the author(s)

Identifiers

Citation

Marek Klonowski, Dominik Pajak. On λ-Alert Problem. IPDPS - 26th IEEE International Parallel and Distributed Processing Symposium, May 2012, Shanghai, China. pp.1057-1067, ⟨10.1109/IPDPS.2012.98⟩. ⟨hal-00996841⟩

Share

Metrics

Record views

280

Files downloads

127