Mengapa konsensus dianggap sebagai masalah tersulit dalam sistem terdistribusi?

Karena banyak tugas koordinasi lainnya—siaran atomik, mesin status tereplikasi, penguncian terdistribusi—bermuara pada konsensus, dan konsensus itu sendiri terbukti tidak mungkin dipecahkan secara deterministik dalam model kegagalan crash asinkron, sehingga setiap solusi harus membuat asumsi waktu atau keacakan yang cermat.

Bagaimana konsensus berhubungan dengan basis data tereplikasi?

Basis data tereplikasi menjaga konsistensi replikanya dengan menyepakati urutan operasi, yang merupakan urutan keputusan konsensus; inilah mengapa sistem seperti penyimpanan kunci-nilai terdistribusi menyematkan protokol konsensus pada intinya.

Konsensus dan Koordinasi

Konsensus dan koordinasi membahas bagaimana proses-proses independen yang berkomunikasi hanya melalui pesan dapat menyepakati suatu nilai atau tindakan bersama meskipun ada penundaan dan kegagalan.

Temukan Topik dengan PaperMindSegeraFind papers & topics

Tools & resources

Unduh salindia

Learn & explore

VideoSegera

Definition

Konsensus adalah masalah di mana sekumpulan proses, masing-masing mengusulkan suatu nilai, semuanya memutuskan satu nilai umum sedemikian rupa sehingga keputusan tersebut valid, semua proses yang benar sepakat, dan setiap proses yang benar pada akhirnya memutuskan, bahkan ketika beberapa proses gagal.

Scope

Area ini mencakup masalah konsensus dan variannya (kesepakatan, siaran atomik, validitas, terminasi), hasil kemustahilan FLP yang mendasar untuk konsensus asinkron deterministik, protokol konsensus praktis seperti Paxos dan Raft, kesepakatan toleran kesalahan Bizantium, dan masalah koordinasi klasik berupa pengecualian bersama dan pemilihan pemimpin. Ini adalah inti teoretis dan praktis dari komputasi terdistribusi yang toleran terhadap kesalahan.

Sub-topics

Core questions

Dalam model waktu dan kegagalan apa konsensus dapat dipecahkan, dan kapan terbukti tidak mungkin?
Bagaimana protokol praktis menghindari kemustahilan FLP sambil menjaga keamanan?
Berapa banyak replikasi yang diperlukan untuk mentoleransi kegagalan crash versus Bizantium?
Bagaimana proses dapat mengoordinasikan akses ke sumber daya bersama atau memilih pemimpin secara andal?

Key theories

Kemustahilan FLP: Dalam sistem yang sepenuhnya asinkron, tidak ada protokol deterministik yang dapat menjamin konsensus jika bahkan satu proses pun dapat crash, karena proses yang lambat tidak dapat dibedakan dari proses yang gagal; hasil ini memotivasi sinkroni parsial, randomisasi, dan detektor kegagalan.
Konsensus berbasis kuorum: Protokol seperti Paxos mencapai kesepakatan dengan mensyaratkan mayoritas yang tumpang tindih (kuorum) untuk menerima proposal, memastikan bahwa setiap dua keputusan berpotongan pada proses yang benar dan dengan demikian tetap konsisten di seluruh putaran dan perubahan pemimpin.
Batasan kesepakatan Bizantium: Untuk mencapai kesepakatan ketika hingga f proses dapat berperilaku sewenang-wenang, setidaknya 3f+1 proses diperlukan dalam pengaturan sinkron klasik, batasan ketat yang membentuk desain semua sistem toleran kesalahan Bizantium.

Clinical relevance

Konsensus adalah tulang punggung infrastruktur yang andal: layanan koordinasi, basis data tereplikasi, kunci terdistribusi, dan blockchain semuanya menjalankan protokol konsensus untuk menjaga konsistensi replika, menjadikan area ini bertanggung jawab langsung atas jaminan durabilitas dan ketersediaan sistem cloud modern.

History

Makalah jenderal Bizantium tahun 1982 dan hasil kemustahilan FLP tahun 1985 membingkai batasan kesepakatan; Paxos Lamport (diedarkan pada tahun 1989, diterbitkan pada tahun 1998) memberikan protokol asinkron-aman yang praktis, dan pekerjaan selanjutnya tentang toleransi kesalahan Bizantium dan Raft membuat konsensus menjadi tangguh terhadap kesalahan berbahaya dan dapat diakses oleh para pengimplementasi.

Debates

Apakah kemustahilan FLP membuat konsensus tidak dapat dicapai dalam praktik?: FLP mengesampingkan protokol deterministik yang selalu aman dan hidup dalam model yang sepenuhnya asinkron, tetapi sistem praktis mengesampingkannya dengan mengasumsikan sinkroni eventual atau menggunakan randomisasi, menjaga keamanan tanpa syarat dan mencapai kelangsungan hidup kapan pun jaringan berperilaku.

Key figures

Leslie Lamport
Nancy Lynch
Michael Fischer
Michael Paterson
Barbara Liskov

Seminal works

fischer1985
lamport1998
lamport1982byz

Frequently asked questions

Mengapa konsensus dianggap sebagai masalah tersulit dalam sistem terdistribusi?: Karena banyak tugas koordinasi lainnya—siaran atomik, mesin status tereplikasi, penguncian terdistribusi—bermuara pada konsensus, dan konsensus itu sendiri terbukti tidak mungkin dipecahkan secara deterministik dalam model kegagalan crash asinkron, sehingga setiap solusi harus membuat asumsi waktu atau keacakan yang cermat.
Bagaimana konsensus berhubungan dengan basis data tereplikasi?: Basis data tereplikasi menjaga konsistensi replikanya dengan menyepakati urutan operasi, yang merupakan urutan keputusan konsensus; inilah mengapa sistem seperti penyimpanan kunci-nilai terdistribusi menyematkan protokol konsensus pada intinya.