A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors. Distributed algorithms are used in different application areas of distributed computing, such as telecommunications, scientific computing, distributed information processing, and real-time process control. Standard problems solved by distributed algorithms include leader election, consensus, distributed search, spanning tree generation, mutual exclusion, and resource allocation.
Distributed algorithms are a sub-type of parallel algorithm, typically executed concurrently, with separate parts of the algorithm being run simultaneously on independent processors, and having limited information about what the other parts of the algorithm are doing. One of the major challenges in developing and implementing distributed algorithms is successfully coordinating the behavior of the independent parts of the algorithm in the face of processor failures and unreliable communications links. The choice of an appropriate distributed algorithm to solve a given problem depends on both the characteristics of the problem, and characteristics of the system the algorithm will run on such as the type and probability of processor or link failures, the kind of inter-process communication that can be performed, and the level of timing synchronization between separate processes.
Atomic commit
An atomic commit is an operation where a set of distinct changes is applied as a single operation. If the atomic commit succeeds, it means that all the changes have been applied. If there is a failure before the atomic commit can be completed, the "commit" is aborted and no changes will be applied.
Algorithms for solving the atomic commit problem include the two-phase commit protocol and the three-phase commit protocol.
Consensus
Consensus algorithms try to solve the problem of a number of processes agreeing on a common decision.
More precisely, a Consensus protocol must satisfy the four formal properties below.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
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.
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.
Le prix Edsger W. Dijkstra en algorithmique répartie, anciennement prix PoDC de l'article influent, est décerné chaque année, depuis 2000, aux auteurs d'un article dont l'impact est particulièrement important pour la théorie ou la pratique des systèmes distribués depuis au moins dix ans. Remis à l'origine lors de la conférence ACM Principles of Distributed Computing (PoDC), il est, depuis 2007, remis alternativement lors de PoDC les années paires et lors de la conférence EATCS Distributed Computing (DISC) les années impaires, chacune des deux conférences fournissant la moitié de la somme de .
Software agents are widely used to control physical, economic and financial processes. The course presents practical methods for implementing software agents and multi-agent systems, supported by prog
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 machin
With the advent of multiprocessors, it becomes crucial to master the underlying algorithmics of concurrency. The objective of this course is to study the foundations of concurrent algorithms and in pa
Within only a couple of generations, the so-called digital revolution has taken the world by storm: today, almost all human beings interact, directly or indirectly, at some point in their life, with a
Explique l'accord de réseau dans les algorithmes distribués, en se concentrant sur les processus d'accord sur les décisions malgré les échecs.
Explore l'algorithme FloodSet pour parvenir à un consensus dans les systèmes distribués grâce à des preuves guidées et à une analyse de la complexité de la communication.
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.