Programme
1. DESCRIPTION DU COURS
Le problème du consensus est un problème fondamental en théorie du calcul distribué. Il consiste pour un ensemble de processus à se mettre d'accord sur une valeur de sortie. Les applications sont très nombreuses puisque la résolution de ce problème est primordiale pour la coordination des systèmes distribués. Dans ce cours, il est proposé de repartir de cette notion fondamentale et des besoins correspondants notamment en réplication de bases de données pour aborder les développements récents des systèmes de type blockchain.
2. PLAN DU COURS
CM : 14h TD+TP :3h
1. Introduction au systèmes distribué (3h30 CM) : définition d'un système distribué (notion de processus modèles de communication par message ou mémoire partagée, système synchrone ou asynchrone), définition de fautes (perte de messages, crash de processus, processus byzantins), tâches distribuées, problème du consensus (notion de terminaison, intégrité et accord) (3)
2. Étude d'un algorithme de consensus à l'aide d'un simulateur : raft (1) (3h TD/TP)
3. Impossibilité du consensus asynchrone en cas de crash (2) (3h CM)
4. Algorithme de consensus en présence de processus byzantins (3+4) (3h CM)
5. Résolution du « consensus byzantin » dans la blockchain : preuve de travail, preuve d'enjeux (3h30CM)
6. Conclusions et perspectives (1h CM)
3. RÉFÉRENCES
1. In Search of an Understandable Consensus Algorithm. Diego Ongaro and John K.
Ousterhout. 2014. USENIX Annual Technical Conference. pp. 305-319.
2. Impossibility of distributed consensus with one faulty process. Fischer, Michael J., Nancy A. Lynch, and Michael S. Paterson. 1985, Journal of the ACM (JACM), Vol. 32.2, pp. 374-382.
3. Distributed Algorithms, Nancy Lynch., Morgan Kaufmann. 1996
4. The Byzantine Generals Problem, Leslie Lamport, Robert Shostak et Marshall Pease, ACM
Transactions on Programming Languages and Systems, vol. 4, no 3, 1982
