Algorithmes épidémiques pour la maintenance de bases de données répliquées

Lorsque cette base de données est répliquée sur de nombreux sites, le maintien de la cohérence mutuelle entre les sites face aux mises à jour est un problème significatif. Cet article décrit plusieurs algorithmes randomisés pour distribuer les mises à jour et amener les répliques vers la cohérence. Les algorithmes sont très simples et nécessitent peu de garanties du système de communication sous-jacent, et néanmoins ils garantissent que l'effet de chaque mise à jour est finalement reflété dans toutes les répliques. Le coût et les performances des algorithmes sont ajustés en choisissant des distributions appropriées dans l'étape de randomisation. Ces algorithmes sont étroitement analogues aux épidémies, et l'épidémiologie aide à comprendre leur comportement. L'un des algorithmes a été implémenté dans le service de Clearinghouse de la société Xerox, résolvant des problèmes de longue date de trafic élevé et d'incohérence des données.