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.
Type de document :
Communication dans un congrès
IPDPS - 26th IEEE International Parallel and Distributed Processing Symposium, May 2012, Shanghai, China. IEEE, pp.1057-1067, 2012, IPDPS. 〈10.1109/IPDPS.2012.98〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00996841
Contributeur : Dominik Pajak <>
Soumis le : mardi 27 mai 2014 - 09:30:09
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12
Document(s) archivé(s) le : mercredi 27 août 2014 - 11:01:03

Fichier

ipdps.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

237

Téléchargements de fichiers

97