TOKEN TRANSFER IN A FAULTY NETWORK

摘要

A token originally situated in a given fault-free node of the complete network, called the source, has to visit all other fault-free nodes. Links and/or nodes of the network fail independently with probabilities p < 1 and q < 1, respectively. In a unit of time every node can be involved in at most one transmission; transmissions along a faulty link or involving a faulty node do not succeed. We consider various communication models depending on the ability of nodes to modify their behavior according to the outcome of previous transmissions. For all models we present token transfer algorithms working fast and with probability of correctness exceeding 1 — n~(-ε), where n is the number of nodes and ε an arbitrary positive constant.%Un jeton, situé d''abord dans un nœud fonctionnel d''un réseau complet, appelé la source, doit visiter tous les autres nœuds fonctionnels. Les liens et/ou les nœuds du réseau tombent en panne avec probabilités p < 1 et q < 1 respectivement ; toutes les pannes sont indépendantes. Pendant une unité de temps chaque noeud peut participer à au plus une transmission ; les transmissions dans lesquelles participe un nœud ou un lien défectueux n ''ont aucun effet. Nous considérons plusieurs modèles de communication selon la capacité des nœuds à modifier leur comportement compte tenu des résultats des transmissions antérieures. Pour tous les modèles nous présentons des algorithmes de transfert du jeton qui sont à la fois rapides et qui travaillent correctement avec probabilité plus grande que 1 — n~(-ε), où n est le nombre des nœuds et ε est une constante positive quelconque.