Séance de cours

Algorithmes de consensus: FloodSet

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

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.

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 (18)

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.

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.

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.

Afficher plus

Séances de cours associées (48)

Algorithme FloodSet : consensus et accord

Explore l'algorithme FloodSet pour un accord synchrone en cas de panne et sa complexité de communication, ainsi que des exercices bonus sur les protocoles de consensus.

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.

Système d'exécution distribué à usage général

Examine la conception d'un système d'exécution distribué à usage général, couvrant les défis, les cadres spécialisés, la logique de contrôle décentralisée et les remaniements de haute performance.

Complexité des algorithmes

Explore la complexité des algorithmes, analyse l'efficacité et les pires scénarios des algorithmes de tri.

Afficher plus

Concepts associés (18)

Calcul distribué

Algorithmique répartie

Computational complexity

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

Problème du consensus

Afficher plus