Ordonnancement des messages et multidiffusion
La communication de groupe délivre un message à un ensemble de processus avec des garanties de fiabilité et d'ordonnancement spécifiées, allant du FIFO à l'ordre total, en passant par l'ordre causal.
Definition
La multidiffusion délivre un message unique à chaque membre d'un groupe de processus ; les garanties d'ordonnancement contraignent l'ordre de livraison relatif des messages, le FIFO préservant l'ordre par émetteur, le causal préservant l'ordre « happened-before » (avant-après), et l'ordre total délivrant tous les messages dans la même séquence à chaque membre.
Scope
Ce sujet couvre la multidiffusion fiable et la hiérarchie des ordonnancements de livraison — FIFO, causal et total (atomique) —, leurs implémentations utilisant des numéros de séquence, des horloges logiques et des schémas de séquenceur ou de jeton, ainsi que le modèle de synchronie virtuelle qui intègre la multidiffusion ordonnée avec des changements cohérents d'appartenance au groupe. Il est démontré que la diffusion d'ordre total (atomique) est équivalente en puissance au consensus.
Core questions
- Quelles garanties de fiabilité et d'ordonnancement une application requiert-elle de la communication de groupe ?
- Comment les ordres de livraison causal et total sont-ils implémentés efficacement ?
- Pourquoi la diffusion d'ordre total est-elle équivalente au consensus ?
Key theories
- Hiérarchie d'ordonnancement
- Les ordonnancements de livraison forment une hiérarchie — le FIFO est plus faible que le causal, qui est lui-même plus faible que l'ordre total — chacun étant appliqué par des métadonnées supplémentaires telles que des numéros de séquence par émetteur, des horodatages vectoriels ou une séquence globalement convenue.
- Synchronie virtuelle
- La synchronie virtuelle présente les changements d'appartenance au groupe et les messages de multidiffusion dans un ordre cohérent à tous les membres, de sorte que les processus voient la même séquence d'événements et de changements de vue, ce qui simplifie la construction de services répliqués.
- La diffusion atomique équivaut au consensus
- La diffusion d'ordre total (atomique) et le consensus sont réductibles l'un à l'autre ; par conséquent, toute solution à l'un produit une solution à l'autre, et les deux partagent les mêmes limites de résolvabilité en présence d'asynchronisme et de défaillances.
Clinical relevance
La multidiffusion ordonnée et fiable est le substrat de la réplication de machines à états, des systèmes de publication-abonnement et des bases de données répliquées, où chaque réplique doit appliquer les mêmes mises à jour dans le même ordre pour maintenir sa cohérence.
History
Birman et Joseph ont introduit la synchronie virtuelle et la multidiffusion ordonnée dans les années 1980 via le système ISIS ; la relation entre la diffusion atomique et le consensus a été clarifiée dans les années 1990, et l'étude de Defago, Schiper et Urban de 2004 a systématisé les nombreux algorithmes d'ordre total.
Key figures
- Kenneth Birman
- Thomas Joseph
- Andre Schiper
- Leslie Lamport
Related topics
Seminal works
- birman1987
- defago2004
- lamport1978
Frequently asked questions
- Quelle est la différence entre l'ordonnancement causal et l'ordonnancement total ?
- L'ordonnancement causal ne contraint que les messages qui sont causalement liés, laissant les messages concurrents libres d'être délivrés dans des ordres différents par différents processus. L'ordonnancement total exige que chaque processus délivre tous les messages dans la même séquence identique, ce qui est strictement plus fort et aussi difficile que le consensus.