La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Sub-Linear Time Aggregation in Probabilistic Population Protocol Model Agrégation temporelle sous-linéaire dans le modèle de protocole de population probabiliste

Ryota EGUCHI, Taisuke IZUMI

  • Vues en texte intégral

    0

  • Citer

Résumé:

Un système passivement mobile est une notion abstraite de réseaux mobiles ad hoc. Il s'agit d'un ensemble d'agents dotés d'appareils informatiques. Les agents se déplacent dans une région, mais l'algorithme ne peut pas contrôler leur comportement physique (c'est-à-dire la façon dont ils se déplacent). Le modèle de protocole de population est l'un des modèles prometteurs dans lequel le calcul se fait par communication par paires entre deux agents. Les agents communicants mettent à jour leurs états par une fonction de transition spécifiée (algorithme). Dans cet article, nous considérons une forme générale de agrégation problème avec une station de base. La station de base est un agent spécial doté d’une puissance de calcul plus puissante que les autres. Dans le problème d'agrégation, la station de base doit résumer les entrées distribuées aux autres agents. Nous proposons un algorithme qui résout le problème d'agrégation en temps parallèle sous-linéaire en utilisant un nombre relativement faible d'états par agent. Plus précisément, notre algorithme résout le problème d'agrégation avec le domaine d'entrée X in O(√n enregistrer2 n) temps parallèle et O(|X|2) états par agent (sauf pour la station de base) avec une forte probabilité.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1187-1194
Date de publication
2019/09/01
Publicisé
ISSN en ligne
1745-1337
DOI
10.1587/transfun.E102.A.1187
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories
Algorithmes distribués

Auteurs

Ryota EGUCHI
  Nagoya Institute of Technology
Taisuke IZUMI
  Nagoya Institute of Technology

Mots-clés

Table des matières