Résoudre un consensus pour un nombre connu de processus
-
04-11-2019 - |
Question
On m'a donné un objet avec exactement 2 opérations test-and-reset
qui définit la valeur de l'objet à 0 uniquement si elle était précédemment définie sur 1 et ne renvoie pas de valeur et fetch-and-add(v)
qui ajoute v
à la valeur de l'objet et renvoie la valeur précédente.
Je suis presque sûr que le numéro de consensus de cet objet est 2 et je pense que j'ai trouvé un algorithme pour cela (je dois mentionner que le problème est un consensus binaire):
if input = 0
test-and-reset(obj)
prev = fetch-and-add(obj, 3)
if (prev != 2)
decide(0)
else
decide(1)
else
prev = fetch-and-add(obj, 1)
if (prev = 0 or prev = 3)
decide(0)
else
decide(1)
Le problème était de trouver un algorithme sans attente pour un algorithme pour n
processus utilisant n'importe quel nombre de ces objets (n
est connu).
Le problème est que je ne sais pas si j'ai raison (je suis presque sûr et cela me retient sur cette idée)? Et si j'ai raison, je ne sais pas comment l'utiliser pour résoudre le problème.
Merci
Pas de solution correcte