Skip to Main content Skip to Navigation
New interface
Conference papers

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 metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Dominik Pajak Connect in order to contact the contributor
Submitted on : Tuesday, May 27, 2014 - 9:30:09 AM
Last modification on : Saturday, June 25, 2022 - 7:46:16 PM
Long-term archiving on: : Wednesday, August 27, 2014 - 11:01:03 AM


Files produced by the author(s)




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⟩



Record views


Files downloads