3 Réponses :
c'est-à-dire - d (l'ensemble des configurations possibles après l'application E sur des éléments de C ) contient à la fois des configurations 0-SALENT et 1 SALENT ( et est supposé ne contenir aucune configuration bivalente).
E Maps chaque élément de C à une configuration 0-SALENT ou 1 SALENT. Par définition de C , il doit y avoir un élément racine qui est connecté à tous les autres éléments par une série de relations "voisines", donc là-bas c qui conduit à une configuration 0-valent après E est voisin avec un élément dans C qui conduit à une configuration à 1 valent E .
Qu'est-ce qu'un élément dans une configuration? Plus spécifiquement, qu'est-ce qu'un élément racinaire?
Je suppose que "l'élément" est ici le "processeur" mentionné dans le document. Mais je m'inquiète de la définition de "élément racinaire", aussi? Pouvez-vous clarifier cela?
Par définition de C, il doit y avoir un élément racine qui est connecté à tous les autres éléments par une série de relations "voisines", et pourquoi la définition de C peut conduire à cette déclaration?
J'utilisais la langue de la question. C dans la question et dans ma réponse correspond à \ mathscr {c} dans le papier. Il s'agit d'un ensemble de configurations définies par "let \ mathscr {c} être l'ensemble des configurations accessibles de C sans appliquer e". Les éléments de \ mathscr {c} sont des configurations. La définition de \ mathscr {c} le décrit comme un ensemble de configurations accessibles, c'est-à-dire un ensemble d'éléments qui sont tous connectés par des relations "voisine".
Définir un mappage parce que Arrangez des configurations accessibles à partir de la configuration bivalente initiale dans un arbre, il doit y avoir deux voisins C0, C1 dans l'arborescence que f tel que f (C) = 0 , si E (c) est 0-SALENT, sinon, < Code> F (C) = 1 , si E (c) est 1-SALENT.
e (c) n'a pas pu être bivalent, si nous supposons que d n'a pas de configuration bivalente, f (c) pourrait seulement être 0 ou 1.
F (C0)! = F (C1) . Parce que, sinon, tous les f (c) sont identiques, ce qui signifie que d n'a que toutes les configurations 0-SALENT ou toutes les configurations à 1 valent.
J'ai déjà descendu le chemin de la lecture de tous ces papiers pour découvrir sa perte de temps complète.
Le résultat n'est pas surprenant du tout.
Le papier que vous mentionnez "[impossibilité de consensus distribué avec une faute Processus] " 1
est une longue liste de preuves mathématiques complexes qui équivalent simplement à:
1) consensus est un état déterministe
2) Un (ou plusieurs) systèmes défectueux dans un environnement est un environnement non déterministe
3) Aucun état déterministe, action ou résultat ne peut jamais être atteint dans un environnement non déterministe.
la fin. Aucune autre pensée n'est requise.
Voici comment cela fonctionne dans le monde réel en dehors de Acadamia.
Si vous souhaitez que les agents atteignent un consensus, des constructions de rapprochement synchrones (modélisation) doivent être ajoutées pour rendre l'environnement déterministe dans un ensemble de contraintes donné. Par exemple, des constructions simples telles que les délais d'attente, ACK / Nack, Handshake, Témoin ou des constructions plus complexes.
Plus vous souhaitez accéder à un modèle déterministe synchrone, plus les constructions sont complexes. Un modèle synchrone hypothétique aurait des constructions infiniment complexes. Gardant également à l'esprit qu'un modèle synchrone déterministe ne peut jamais être atteint dans un système distribué non trivial. En effet, dans tout système multi-variable dynamique non trivial avec un état initial variable, il existe un nombre infini d'états, d'actions et de résultats éventuels à tout moment. Théorie Chaos
Considérez la complexité d'une construction de la détection de paquets TCP déposés en raison d'erreurs de débordement tampon dans un routeur au numéro 21. Et la complexité de la détection de la même erreur de débordement tampon dépose le signal de détection de la construction elle-même.
Ce lemme spécifique est le cœur de cet article et j'ai observé qu'il a été utilisé de manière approfondie pour prouver le numéro de consensus d'un objet de synchronisation dans un autre papier "Synchronisation sans attente" par Herlihy.