Exclusion mutuelle distribuée et élection de leader

L'exclusion mutuelle et l'élection de leader sont des problèmes de coordination classiques : garantir qu'au plus un processus accède à une ressource critique, et sélectionner un unique coordinateur distingué parmi les pairs.

Definition

L'exclusion mutuelle distribuée garantit qu'au plus un processus à la fois détient une ressource partagée tout en assurant un accès éventuel à tous les demandeurs ; l'élection de leader sélectionne de manière déterministe exactement un processus comme coordinateur, tous les processus s'accordant sur le résultat.

Scope

Ce sujet couvre les algorithmes d'exclusion mutuelle basés sur les permissions (algorithme d'horodatage de Lamport, Ricart-Agrawala, approche par quorum de Maekawa) et les algorithmes basés sur les jetons, ainsi que leur complexité de message et leurs propriétés d'équité ; et les algorithmes d'élection de leader pour les anneaux (Chang-Roberts) et les réseaux généraux (l'algorithme du tyran), y compris leurs hypothèses concernant les identifiants et la synchronie. Ces primitives sont récurrentes dans les services de coordination et les systèmes répliqués.

Core questions

• Comment les processus peuvent-ils sérialiser l'accès à une ressource partagée en utilisant uniquement des messages ?
• Quels sont les compromis en termes de complexité de message et d'équité entre les schémas basés sur les permissions et ceux basés sur les jetons ?
• Comment un leader unique est-il choisi, et comment l'élection est-elle redéclenchée après la défaillance du leader ?

Key theories

Exclusion mutuelle basée sur les permissions

Des algorithmes tels que Ricart-Agrawala ordonnent les requêtes par horodatages logiques et accordent l'entrée une fois qu'un demandeur a reçu la permission de tous (ou d'un quorum de) ses pairs, atteignant l'équité avec un coût de message borné par entrée en section critique.

Exclusion mutuelle basée sur les jetons

Un jeton unique circule ou est demandé à la demande, et seul son détenteur peut entrer dans la section critique, ce qui réduit le trafic de messages mais nécessite des mécanismes pour régénérer un jeton perdu après des défaillances.

Élection de leader

Les algorithmes d'élection tels que Chang-Roberts pour les anneaux et l'algorithme du tyran pour les réseaux généraux utilisent des identifiants de processus pour converger vers un unique coordinateur de plus haute priorité que tous les processus corrects reconnaissent.

Clinical relevance

L'élection de leader est invoquée chaque fois qu'un système répliqué doit choisir un primaire ou un coordinateur, et le verrouillage distribué généralise l'exclusion mutuelle ; les deux sont exposés comme des services fondamentaux par les systèmes de coordination utilisés dans toute l'infrastructure cloud.

History

L'article de Lamport de 1978 sur les horloges logiques a introduit un algorithme d'exclusion mutuelle basé sur les horodatages ; Ricart et Agrawala l'ont optimisé en 1981, Maekawa a introduit les quorums peu après, et l'algorithme du tyran de Garcia-Molina de 1982 a formalisé l'élection de leader, dotant ainsi le domaine de ses algorithmes de coordination canoniques.

Key figures

• Leslie Lamport
• Glenn Ricart
• Ashok Agrawala
• Hector Garcia-Molina

Seminal works

• ricart1981
• garcia-molina1982
• lynch1996

Frequently asked questions

En quoi l'exclusion mutuelle distribuée diffère-t-elle d'un verrou sur une seule machine ?

Il n'y a pas de mémoire partagée ou de gestionnaire de verrou central sur lequel s'appuyer, de sorte que les processus doivent se coordonner uniquement par l'échange de messages et doivent gérer explicitement les délais de message et les défaillances, ce qu'un verrou sur une seule machine peut considérer comme acquis.