Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Algorithmes de consensus: FloodSet

Dans cours

CS-451: Distributed algorithms

Computing is nowadays distributed over several machines, in a local IP-like network, a cloud or a P2P network. Failures are common and computations need to proceed despite partial failures of machines or communication links. This course will study the fo ...

Description

Cette séance de cours couvre l'algorithme FloodSet, une solution simple au problème de l'accord pour les pannes dans les systèmes distribués. L'algorithme implique des processus de propagation de valeurs et l'utilisation d'une règle de décision pour parvenir à un consensus. Grâce à des preuves guidées, la séance de cours démontre l'exactitude de FloodSet dans la réalisation de l'accord, de la validité et de la résiliation. En outre, il explore la complexité de la communication de l'algorithme et discute des règles de décision alternatives. Les exercices bonus introduisent un cadre unique pour le consensus dans un réseau de grille à deux dimensions, mettant au défi les étudiants de concevoir des protocoles optimisés pour parvenir à un consensus en présence de processus défectueux.

Cette vidéo est disponible exclusivement sur Mediaspace pour un public restreint. Veuillez vous connecter à Mediaspace pour y accéder si vous disposez des autorisations nécessaires.

Regarder sur Mediaspace

Enseignant·e

Rachid Guerraoui

Rachid Guerraoui has been affiliated with Ecole des Mines of Paris, the Commissariat à l'Energie Atomique of Saclay, Hewlett Packard Laboratories and the Massachusetts Institute of Technology. He has worked in a variety of aspects of distributed computing, including distributed algorithms and distributed programming languages. He is most well known for his work on (e-)Transactions, epidemic information dissemination and indulgent algorithms. He co-authored a book on Transactional Systems (Hermes) and a book on reliable distributed programming (Springer). He was appointed program chair of ECOOP 1999, ACM Middleware 2001, IEEE SRDS 2002, DISC 2004 and ACM PODC 2010. His publications are available at http://lpdwww.epfl.ch/rachid/papers/generalPublis.html

Source officielle

Concepts associés (14)

Calcul distribué

Un calcul distribué, ou réparti ou encore partagé, est un calcul ou un traitement réparti sur plusieurs microprocesseurs et plus généralement sur plusieurs unités centrales informatiques, et on parle alors d'architecture distribuée ou de système distribué. Le calcul distribué est souvent réalisé sur des clusters de calcul spécialisés, mais peut aussi être réalisé sur des stations informatiques individuelles à plusieurs cœurs. La distribution d'un calcul est un domaine de recherche des sciences mathématiques et informatiques.

Algorithmique répartie

Un algorithme réparti (ou distribué) est une suite d'instructions et il est généralement un algorithme parallèle (mais pas toujours, exemple, une communication téléphonique) réparti sur plusieurs sites. Chaque site calcule (i.e. produit de nouveaux résultats) et communique (i.e. échange des données avec d'autres sites). Un algorithme réparti décrit le fonctionnement d'un système informatique composé de plusieurs unités de calcul reliées par un réseau de communication, tels que les routeurs dans Internet.

Problème du consensus

Le problème du consensus est un problème fondamental en théorie du calcul distribué. Il consiste pour un ensemble de machines à se mettre d'accord sur une valeur ou, par extension, sur une séquence de valeurs. La résolution du consensus est primordiale pour la coordination des systèmes distribués. Elle permet notamment la consistance des systèmes répliqués malgré la défaillance d'une partie de leurs composants.

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Théorie de la complexité (informatique théorique)

vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée ...) requis par un algorithme pour résoudre un problème algorithmique.

Afficher plus

Séances de cours associées (26)

Complexité et induction: Algorithmes et preuves

Couvre la complexité, les algorithmes et les preuves du pire cas, y compris l'induction mathématique et la récursion.

Informatique quantique distribuée

Explore la complexité de la communication et les modèles de calcul quantique dans Distributed Quantum Computing.

Communication au milieu de l'incertitude

Explore les défis dans la communication humaine, l'importance du contexte, les problèmes de compression, la fonctionnalité incertaine et la vérification des preuves.

Réplication et consensus dans les systèmes distribués

Explore la réplication, le consensus, l'algorithme Paxos, le consensus majoritaire et la réservation d'arrêt dans les systèmes distribués.

Information, calcul et société

Explore l'histoire et l'impact sociétal des sciences de l'information, de la communication et de l'informatique à l'ère numérique.

Afficher plus

Concepts associés (14)

Calcul distribué

Algorithmique répartie

Problème du consensus

Computational complexity

Théorie de la complexité (informatique théorique)

Afficher plus