On the Necessary Memory to Compute the Plurality in Multi-Agent Systems

Abstract : We consider the Relative-Majority Problem (also known as Plurality), in which, given a multi-agent system where each agent is initially provided an input value out of a set of $k$ possible ones, each agent is required to eventually compute the input value with the highest frequency in the initial configuration. We consider the problem in the general Population Protocols model in which, given an underlying undirected connected graph whose nodes represent the agents, edges are selected by a globally fair scheduler. The state complexity that is required for solving the Plurality Problem (i.e., the minimum number of memory states that each agent needs to have in order to solve the problem), has been a long-standing open problem. The best protocol so far for the general multi-valued case requires polynomial memory: Salehkaleybar et al. (2015) devised a protocol that solves the problem by employing $O(k 2^k)$ states per agent, and they conjectured their upper bound to be optimal. On the other hand, under the strong assumption that agents initially agree on a total ordering of the initial input values, Gasieniec et al. (2017), provided an elegant logarithmic-memory plurality protocol. In this work, we refute Salehkaleybar et al.'s conjecture, by providing a plurality protocol which employs $O(k^{11})$ states per agent. Central to our result is an ordering protocol which allows to leverage on the plurality protocol by Gasieniec et al., of independent interest. We also provide a $\Omega(k^2)$-state lower bound on the necessary memory to solve the problem, proving that the Plurality Problem cannot be solved within the mere memory necessary to encode the output.
Type de document :
Chapitre d'ouvrage
Liste complète des métadonnées

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

Contributeur : Emanuele Natale <>
Soumis le : jeudi 11 juillet 2019 - 17:05:40
Dernière modification le : samedi 20 juillet 2019 - 15:58:01


Fichiers produits par l'(les) auteur(s)




Emanuele Natale, Iliad Ramezani. On the Necessary Memory to Compute the Plurality in Multi-Agent Systems. Proceedings of the 11th International Conference Algorithms and Complexity (CIAC 2019), pp.323-338, 0019, ⟨10.1007/978-3-030-17402-6_27⟩. ⟨hal-02002448⟩



Consultations de la notice


Téléchargements de fichiers