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 cohérence des systèmes répliqués malgré la défaillance d'une partie de leurs composants. Le consensus est notamment utilisé pour la réplication d'automates (State Machine Replication), l'exécution de transactions distribuées ou encore au cœur des services de coordination tels que ZooKeeper. Paxos et Raft comptent parmi les algorithmes les plus populaires. Lorsque les pannes sont arbitraires, on parle de consensus Byzantin. Alors que le consensus classique est privilégié au sein des structures contrôlées comme les centres de données, le consensus Byzantin est requis en milieu ouvert dans le contexte des blockchains. PBFT, Tendermint ou encore l'algorithme de Nakamoto résolvent le consensus Byzantin.

Description du problème

Le problème du consensus consiste à concevoir un protocole permettant à un certain nombre de processus de s'accorder sur une valeur unique. Les processus sont sujets à des pannes qui sont de deux types : les pannes bénignes où le processus cesse simplement de fonctionner, et les pannes byzantines ou arbitraires où le processus exécute des opérations arbitraires non prévues par le protocole (volontairement ou non). Les protocoles de consensus doivent être tolérants aux défaillances. Un processus qui ne tombe pas en panne est dit correct.

Formellement, en informatique théorique, un protocole résout le problème du consensus s'il a les propriétés suivantes :

Terminaison
Tout processus qui est correct doit finir par décider une valeur.
Intégrité
Tout processus qui est correct décide une valeur qui a été proposée par un des processus.
Accord
Tous les processus corrects décident la même valeur.

Un protocole qui peut garantir ces propriétés en présence de moins de t pannes est dit t-robuste ou t-resilient.

Consensus binaire et résultat d'impossibilité

Le consensus binaire est le problème du consensus où les processus doivent s'accorder sur une valeur binaire (0 ou 1) en ayant chacun une valeur binaire de départ à proposer. Un des résultats les plus importants de la théorie du calcul distribué, dite impossibilité FLP, est le suivant : Dans un environnement asynchrone où un processus peut faire défaut, le problème du consensus binaire ne peut être résolu par un algorithme déterministe.[1] Ce résultat peut être contourné par l'utilisation d'algorithmes aléatoires qui résolvent le consensus avec probabilité 1 avec un temps d'exécution infini.

Dans les faits, cette impossibilité théorique n'est pas un frein et de nombreux systèmes résolvent le consensus dans des environnements variés.

Nombre de processus fautifs

La résolution du consensus requiert une hypothèse de synchronie. Dans le modèle synchrone, le consensus peut être résolu avec f+1 processus pour tolérer f pannes. Dans le modèle partiellement synchrone, ou avec un détecteur de pannes dont l'exactitude est finalement faible, résoudre le consensus requiert 2f+1 processus.

Dans le modèle synchrone, le consensus Byzantin requiert 2f+1 processus pour tolérer f pannes. Dans le modèle partiellement synchrone, il requiert 3f+1 processus. En rendant impossible l'équivocation des processus, par l'utilisation de composants de confiance comme des enclaves ou une mémoire partagée protégée, le consensus Byzantin peut être résolu avec 2f+1 processus dans le modèle partiellement synchrone.

Références

  1. (en) Michael J. Fischer, Nancy A. Lynch et Michael S. Paterson, « Impossibility of Distributed Consensus with One Faulty Process », Journal of the ACM, Association for Computing Machinery, vol. 32, no 2,‎ , p. 374–382 (ISSN 0004-5411, DOI 10.1145/3149.214121, lire en ligne, consulté le )

Pour aller plus loin


Read other articles:

رونيت القبص (بالعبرية: רונית אלקבץ)‏  معلومات شخصية الميلاد 27 نوفمبر 1964(1964-11-27)بئر السبع الوفاة 19 أبريل 2016 (51 سنة)تل أبيب  سبب الوفاة سرطان الرئة[1]  مكان الدفن مقبرة كريات شاؤول  [لغات أخرى]‏  الجنسية إسرائيلية عدد الأولاد 2   إخوة وأخوات شلومي القبص ...

 

Asbabun Nuzul Surat Ali-'Imran memuat sebab-sebab turunnya sebagian ayat-ayat pada surat Ali-'Imran.[1] Ali-'Imran Ali-'Imran: 77 1. Imam Bukhari meriwayatkan (5/430): ... dari 'Abdullah, dari Nabi saw, dia bersabda:Siapa yang bersumpah untuk merampas harta seseorang dalam keadaan dia sengaja dusta, niscaya dia bertemu Allah dalam keadaan murka kepadanya. Maka Allah ta'ala menurunkan: Sesungguhnya orang-orang yang menukar janji(nya dengan) Allah dan sumpah-sumpah mereka dengan harga y...

 

Наводнение в Европе (2013) Наводнение в Хемнице, Германия, 2 июня 2013 года Описание Период май — июнь 2013 Совокупный ущерб €12 млрд[1] Погибшие по меньшей мере 24[2] Зоны бедствия  Австрия,  Чехия,  Германия, Венгрия,  Польша,  Словакия,  Швейцария,  Украин

Ne doit pas être confondu avec le Frisco Football Classic joué le 23 décembre 2021. Frisco Bowl Généralités Sport Football américain Création 2017 Organisateur(s) NCAA Catégorie Universitaire Périodicité Annuel Lieu(x) Toyota Stadium Frisco, Texas Date Décembre Participants AAC - À déterminer Affluence 20 500 places disponibles Site web officiel Frisco Bowl Palmarès Tenant du titre Boise State Plus titré(s) Kent State (1)Louisiana Tech (1)Ohio (1)San Diego State (1) ...

 

Дель-Кампо — термін, який має кілька значень. Ця сторінка значень містить посилання на статті про кожне з них.Якщо ви потрапили сюди за внутрішнім посиланням, будь ласка, поверніться та виправте його так, щоб воно вказувало безпосередньо на потрібну статтю.@ пошук посилан...

 

Prince of Piedmont Victor AmadeusPrince of PiedmontBorn(1699-05-06)6 May 1699Royal Palace of Turin, TurinDied22 March 1715(1715-03-22) (aged 15)Royal Palace of Turin, TurinBurialRoyal Basilica of Superga, TurinNamesVittorio Amedeo Filippo Giuseppe di SavoiaFatherVictor Amadeus II, Duke of SavoyMotherAnne Marie d'Orléans Victor Amadeus of Savoy (Vittorio Amedeo Filippo Giuseppe;[1][better source needed][2] 6 May 1699 – 22 March 1715) was the eldest son...

селище Пилівка Пылёвка Країна  Росія Суб'єкт Російської Федерації Воронезька область Муніципальний район Панінський район Поселення Краснолиманське сільське поселення Код ЗКАТУ: 20235816008 Код ЗКТМО: 20635416136 Основні дані Населення ▼ 1 (2010)[1] Поштовий індекс 396148 Географ

 

Universitas Negeri MichiganMotoMemajukan Pengetahuan. Mentransformasikan Kehidupan. (Advancing Knowledge. Transforming Lives).Jenis Negeri Hibah tanah Hibah laut Didirikan12 Februari 1855Dana abadi$2,225 milyar (2016)[1]PresidenLou Anna SimonStaf akademik5.300[2]Staf administrasi6.800[2]Jumlah mahasiswa50.543[2]Sarjana39.143[2]Magister11.400[2]LokasiEast Lansing, Michigan, Amerika SerikatKampusPinggiran kota10.000 ekar (40 km2)WarnaHijau da...

 

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (يونيو 2017) تراي ماكيني جونز   معلومات شخصية الميلاد 27 أغسطس 1990 (العمر 33 سنة)ميلواكي الطول 6 قدم 5 بوصة (2.0 م) مركز اللعب مدافع مسدد الهدف  الجنسية  الولايات ...

Kaman SH-2G super Seasprite adalah helikopter berbasis kapal dengan anti-kapal selam, kemampuan ancaman anti-permukaan, termasuk penargetan melampaui cakrawala. Pesawat ini meluaskan dan meningkatkan sensor kapal dan kemampuan senjata terhadap beberapa jenis ancaman musuh, termasuk kapal selam dari semua jenis, kapal permukaan, dan kapal patroli yang dapat dipersenjatai dengan rudal anti-kapal. Ini pada awalnya dikembangkan untuk Angkatan Laut Amerika Serikat pada tahun 1980-an. Misi utama SH...

 

Unicellular organism that lacks a membrane-bound nucleus Diagram of a typical prokaryotic cell A prokaryote (/proʊˈkærioʊt, -ət/) is a single-cell organism whose cell lacks a nucleus and other membrane-bound organelles.[1] The word prokaryote comes from the Ancient Greek πρό (pró) 'before' and κάρυον (káruon) 'nut, kernel'.[2][3] In the two-empire system arising from the work of Édouard Chatton, prokaryotes were classified within the empire Prokaryota....

 

أشانتي كوتوكو الاسم الكامل نادي أشانتي كوتوكو الرياضي اللقب Porcupines (النيص) تأسس عام 1935 (منذ 88 سنة) الملعب ملعب بابا يارا كوماسي، غانا(السعة: 40,500) البلد  غانا الدوري الدوري الغاني الممتاز الإدارة الموقع الرسمي www.asantekotokosc.com الألقاب والأوسمة المحلية الدوري الغاني الممتاز (26) ...

Konsep artis mengenai piringan protoplanet. Sistem keplanetan adalah sekumpulan objek non-bintang yang terikat oleh gravitasi di dalam atau di luar orbit di sekitar sistem bintang atau sistem bintang. Secara umum, sebuah sistem dengan satu atau lebih planet merupakan sistem keplanetan, meskipun sistem tersebut juga dapat terdiri dari benda-benda seperti planet katai, asteroid, satelit alami, meteoroid, komet, planetisimal[1][2] dan piringan lingkar bintang. Matahari bersama de...

 

Perdana Menteri BelandaBelanda: Minister-president van NederlandLambang negara BelandaPetahanaMark Ruttesejak 14 Oktober 2011Kementerian Urusan UmumGelarPerdana MenteriYang TerhormatJenisKepala pemerintahanAnggotaDewan MenteriDewan EropaKediamanCatshuis, Den HaagKantorTorentje, Den HaagDitunjuk olehMonarki BelandaMasa jabatan4 tahun, dapat diperbaruiPejabat pertamaGerrit SchimmelpenninckWakilWakil Perdana MenteriGaji€176.000 per tahun[1]Situs webwww.government.nl/ministries...

 

Contoh skema persilangan balik pada satu sifat beda Persilangan balik (bahasa Inggris: Backcross) adalah suatu jenis yang menunjukkan bahwa kepintaran setiap hewan/manusia itu sangatlah rendah persilangan yang dilakukan di antara keturunan generasi pertama (F1) hasil suatu persilangan dengan salah satu tetuanya.[1] Perbedaan persilangan balik dengan persilangan uji adalah pada silang uji keturunan generasi pertama disilangkan dengan tetua ataupun bukan tetua yang bergentotipe homo...

Diagrama de una batería con un separador de polímero Un separador es una membrana permeable colocada entre el ánodo y el cátodo de una batería. La función principal de un separador es mantener separados los dos electrodos para evitar cortocircuitos eléctricos y, al mismo tiempo, permitir el transporte de portadores de carga iónica que se necesitan para cerrar el circuito durante el paso de corriente en una celda electroquímica.[1]​ Los separadores son componentes críticos en l...

 

Defunct Television channel in the Philippines Television channel O ShoppingHeadquarters9th floor, The Avecshares Center, 1132 University Parkway North, Bonifacio Triangle, Bonifacio Global City, TaguigOwnershipOwnerACJ O Shopping Corporation (a joint-venture of ABS-CBN and CJ ENM O Shopping Division)HistoryLaunchedOctober 14, 2013; 10 years ago (2013-10-14)ClosedNovember 1, 2020; 3 years ago (2020-11-01)[1]Replaced byPIE Channel (Cignal channel spac...

 

Bilateral relationsGeorgian–Kosovar relations Georgia Kosovo Georgian–Kosovar relations are foreign relations between Georgia and Kosovo. Formal diplomatic relations between two states are non-existent as Georgia does not recognize Kosovo as a sovereign state. History The Foreign Minister of Georgia, David Bakradze, said on 18 February 2008 that Tbilisi would not recognise Kosovo's independence, adding: I think everyone in Georgia, regardless of political orientation, is unanimous on this...

Season of television series Season of television series The SimpsonsSeason 31Digital purchase image featuring Brandine SpucklerCountry of originUnited StatesNo. of episodes22ReleaseOriginal networkFoxOriginal releaseSeptember 29, 2019 (2019-09-29) –May 17, 2020 (2020-05-17)Season chronology← PreviousSeason 30Next →Season 32List of episodes The thirty-first season of the animated television series The Simpsons premiered on Fox in the United States on September 29...

 

2021年の日本プロ野球 > 2021年のオリックス・バファローズ 2021年のオリックス・バファローズ成績 日本シリーズ敗退日本S 2勝4敗(対ヤクルト)CSFinal 3勝0敗1分(対ロッテ) パシフィック・リーグ優勝 70勝55敗18分 勝率.560本拠地都市 大阪府大阪市西区球場 京セラドーム大阪 球団組織オーナー 宮内義彦(代行:湊通夫)経営母体 オリックス球団社長 湊通夫GM 福良淳...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!