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

Structure of Initial Conditions for Distributed Algorithms Structure des conditions initiales pour les algorithmes distribués

Naoshi SAKAMOTO

  • Vues en texte intégral

    0

  • Citer

Résumé:

Nous appelons un réseau un réseau anonyme, si chaque sommet du réseau ne reçoit aucun identifiant. Pour les algorithmes distribués pour réseaux anonymes, les problèmes résolubles dépendent fortement des conditions initiales données. Dans le passé, les conditions initiales ont été étudiées, par exemple, par calcul étant donné le nombre de sommets comme condition initiale, et en fonction de la condition initiale nécessaire pour élire un leader. Dans cet article, nous étudions les relations entre les conditions initiales. Pour réaliser cette tâche, nous définissons la relation entre les conditions initiales A et B (dénoté par A B) comme la relation qu'un algorithme distribué peut calculer B sur n'importe quel réseau satisfaisant A. Nous montrons ensuite la propriété suivante de cette relation entre conditions initiales. La relation est un ordre partiel par rapport aux classes d'équivalence. De plus, dans les conditions initiales, il induit un réseau qui a des maxima et des minima et contient un nombre infini d'éléments. En revanche, nous donnons de nouvelles conditions initiales k-CHEF et k-COULEUR. k-CHEF désigne la condition initiale qui donne une condition spéciale uniquement à k sommets. k-COULEUR désigne la condition initiale qui divise les sommets en k groupes. Nous étudions ensuite la propriété de la relation entre ces conditions initiales.

Publication
IEICE TRANSACTIONS on Information Vol.E83-D No.12 pp.2029-2038
Date de publication
2000/12/25
Publicisé
ISSN en ligne
DOI
Type de manuscrit
Special Section INVITED PAPER (Special Issue on the 1999 IEICE Excellent Paper Award)
Catégories
Théorie et modèles de logiciels

Auteurs

Mots-clés

Table des matières