Memory Lower Bounds for Randomized Collaborative Search and Applications to Biology

Ofer Feinerman 1, * Amos Korman 2, 3
* Auteur correspondant
3 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : Initial knowledge regarding group size can be crucial for collective performance. We study this relation in the context of the Ants Nearby Treasure Search (ANTS) problem, which models natural cooperative foraging behavior such as that performed by ants around their nest. In this problem, k (probabilistic) agents, initially placed at some central location, collectively search for a treasure on the two-dimensional grid. The treasure is placed at a target location by an adversary and the goal is to find it as fast as possible as a function of both k and D, where D is the (unknown) distance between the central location and the target. It is easy to see that T = Ω(D + D 2 /k) time units are necessary for finding the treasure. Recently, it has been established that O(T) time is sufficient if the agents know their total number k (or a constant approximation of it), and enough memory bits are available at their disposal [32]. In this paper, we establish lower bounds on the agent memory size required for achieving certain running time performances. To the best our knowledge, these bounds are the first non-trivial lower bounds for the memory size of probabilistic searchers. For example, for every given positive constant ǫ, terminating the search by time O(log 1−ǫ k · T) requires agents to use Ω(log log k) memory bits. Such distributed computing bounds may provide a novel, strong tool for the investigation of complex biological systems.
Type de document :
Communication dans un congrès
Distributed Computing - 26th International Symposium, DISC 2012, Oct 2012, Salvador, Brazil. 〈10.1007/978-3-642-33651-5_5〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01241102
Contributeur : Amos Korman <>
Soumis le : mercredi 6 janvier 2016 - 08:57:02
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Fichiers

Ants-memory-new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Ofer Feinerman, Amos Korman. Memory Lower Bounds for Randomized Collaborative Search and Applications to Biology. Distributed Computing - 26th International Symposium, DISC 2012, Oct 2012, Salvador, Brazil. 〈10.1007/978-3-642-33651-5_5〉. 〈hal-01241102〉

Partager

Métriques

Consultations de la notice

121

Téléchargements de fichiers

39