Mengapa masalah konsensus begitu penting dalam komputasi terdistribusi?

19

Dalam komputasi terdistribusi, masalah konsensus tampaknya menjadi salah satu topik sentral yang telah menarik penelitian intensif. Secara khusus, makalah "Ketidakmungkinan Konsensus Terdistribusi dengan Satu Proses Kerusakan " menerima Penghargaan Kertas Pengaruh PODC tahun 2001 .

Jadi mengapa masalah konsensus begitu penting? Apa yang dapat kita capai dengan konsensus baik dalam teori maupun dalam praktik?

Referensi atau paparan apa pun akan sangat membantu.

reference-request big-picture dc.distributed-comp Hengxin
sumber

Jawaban:

18

Makalah yang Anda sebutkan penting karena 2 alasan:

  1. Ini menunjukkan bahwa tidak ada algoritma konsensus deterministik asinkron yang mentoleransi bahkan satu kesalahan tabrakan. Perhatikan bahwa dalam pengaturan sinkron , ada algoritma deterministik yang berakhir dalam putaran saat memproses crash.≤ ff+1≤f
  2. Ini memperkenalkan bivalensi dan univalensi konfigurasi (*), yang digunakan di banyak batas bawah dan bukti ketidakmungkinan nanti.

Aplikasi

Salah satu aplikasi penting dari masalah konsensus adalah pemilihan koordinator atau pemimpin di lingkungan yang toleran terhadap kesalahan untuk memulai beberapa tindakan global. Algoritma konsensus memungkinkan Anda melakukan ini dengan cepat, tanpa memperbaiki "supernode" terlebih dahulu (yang akan memperkenalkan satu titik kegagalan).

Aplikasi lain adalah menjaga konsistensi dalam jaringan terdistribusi: Misalkan Anda memiliki sensor yang berbeda memantau lingkungan yang sama. Dalam kasus di mana beberapa node sensor ini crash (atau bahkan mulai mengirim data yang rusak karena kesalahan perangkat keras), protokol konsensus memastikan ketahanan terhadap kesalahan tersebut.

(*) Jalankan algoritma terdistribusi adalah urutan konfigurasi. Konfigurasi adalah vektor keadaan lokal dari proses. Setiap proses menjalankan mesin negara deterministik. Algoritma konsensus yang benar pada akhirnya harus mencapai konfigurasi di mana setiap proses telah memutuskan (tidak dapat dibatalkan) pada nilai input yang sama. Sebuah konfigurasi adalah - valent jika, tidak peduli apa yang musuh tidak, semua ekstensi mungkin menyebabkan nilai keputusan . Secara analog, kita dapat mendefinisikan - valensi . Konfigurasi bersifat bivalen jika kedua keputusan dapat dicapai dari1 C 1 0 C C CC1C10CC(yang salah satu dari keduanya tercapai tergantung pada musuh). Jelas, tidak ada proses yang dapat memutuskan dalam konfigurasi bivalen , karena jika tidak kita akan mendapatkan kontradiksi! Jadi jika kita dapat membangun urutan tak terbatas dari konfigurasi bivalen seperti itu, kami telah menunjukkan bahwa tidak ada algoritma konsensus dalam pengaturan ini.C

Peter
sumber
2
@AJed Sebagai pelengkap: Saya telah melirik sinkronisasi kertas oleh Maurice Herlihy dan sekarang dapat menyajikan satu implikasi teoretis tambahan yang bagus dari masalah konsensus. Dengan menggunakan ide nomor konsensus , orang dapat menunjukkan bahwa ada hierarki sinkronisasi primitif tanpa batas, sehingga tidak ada primitif pada satu level yang dapat digunakan untuk implementasi bebas-tunggu dari setiap primitif di level yang lebih tinggi. Sederhananya, masalah konsensus severs sebagai teori terpadu tentang mendefinisikan kekuatan relatif operasi sinkronisasi primitif. Itu elegan.
hengxin
1
Saya mengalami kesulitan dalam memahami bukti hasil ketidakmungkinan FLP. Bisakah Anda memberi saya beberapa petunjuk? Silakan lihat [bukti FLP] ( stackoverflow.com/q/15131730/1833118 ). Terima kasih.
hengxin
"di mana setiap proses telah memutuskan" mungkin harus "di mana setiap proses yang benar telah memutuskan"?
Nbro
Anda harus menjelaskan siapa musuh di "tidak peduli apa yang musuh lakukan".
Nbro
"semua kemungkinan ekstensi C", apa yang Anda maksud dengan "ekstensi C"? Apa yang dimaksud dengan ekstensi konfigurasi, secara umum?
Nbro
7

Ini menunjukkan bahwa tidak ada algoritma deterministik toleran-kesalahan. Cukup hasil teoretis yang kuat, yang memaksa desainer untuk berurusan secara berbeda dengan toleransi kesalahan, beberapa di antaranya adalah sinkronisasi dan pengacakan.

Komentar: Menurut pendapat saya, sinkronisasi adalah asumsi tambahan dari sistem yang sulit ditemukan dalam aplikasi praktis.

Untuk referensi, periksa tautan Wikipedia . Periksa juga blog ini untuk aplikasi praktis

Dipotong
sumber
1
Ya, saya lebih suka pengacakan daripada sinkronisasi. Lingkungan tempat bermain komputasi terdistribusi sangat buruk dalam arti asinkronisasi, penundaan tanpa batas, kegagalan tak terduga, dan terlalu banyak non-deterministik. Selama itu tidak sempurna, mengapa kita tidak menggunakan pengacakan, mencapai beberapa jaminan sambil menghindari terlalu banyak kerumitan.
hengxin
1
Berbicara tentang sinkronisasi, saya hanya tidak menyukai asumsi dalam teori . Namun, dalam industri , sinkronisasi atau sinkronisasi parsial sering diterapkan. Misalnya, Google Spanner adalah basis data yang direplikasi secara sinkron yang didistribusikan secara global . Itu membuat saya kurang tegas. Apa pendapat Anda?
hengxin
Saya kira lebih baik untuk melihat bagaimana sinkronisasi diterapkan di sana. Tapi itu referensi yang sangat menarik. - Maksud saya, ini bukan fitur alami dari sistem. Itu harus ditambahkan padanya.
AJed
Secara umum, Anda tidak boleh memberikan referensi Wikipedia. Saya baru saja membaca artikel Wikipedia itu: itu tidak lengkap dan tidak terorganisir; itu juga bisa membingungkan.
nbro
5

Salah satu alasan masalah konsensus penting adalah bahwa mereka sangat sederhana dan mereka semacam masalah universal untuk sistem komputasi terdistribusi.

Jika kita dapat menyelesaikan konsensus dalam sistem terdistribusi async, kita dapat menggunakannya untuk melegariskan tindakan pada objek yang dibagikan dan mendapatkan kemampuan linierisasi untuk objek yang dibagikan.

Untuk kesederhanaan, berapa banyak masalah yang dapat Anda pikirkan yang lebih sederhana daripada menyetujui suatu nilai?

Hasil ketidakmungkinan tentang konsensus dalam sistem terdistribusi (murni) async memberi tahu kita bahwa kita tidak dapat memecahkan masalah yang ingin kita selesaikan dalam sistem terdistribusi (murni) async tanpa beberapa "barang" tambahan. Ini mengarah ke model async di mana kita dapat menyelesaikan konsensus, misalnya algoritma acak, pendeteksi kesalahan, model sinkronisasi parsial, dll.

Ini juga alasan mengapa dalam praktiknya algoritma yang menyelesaikan konsensus seperti Lamport's Paxos, Google Chubby, Apache ZooKeeper, dan baru-baru ini Raft adalah inti dari sistem terdistribusi di mana kita sering ingin mereplikasi keadaan di antara server.

Kaveh
sumber
0

Saya hanya akan menambahkan bahwa sifat komputasi semakin terdistribusi di seluruh tumpukan: banyak CPU, banyak proses pada mesin, banyak mesin yang terhubung oleh LAN, banyak LAN yang terhubung oleh internet.

Hal ini membuat masalah keadaan negara (terdistribusi / global) menjadi yang terpenting - setiap algoritma mengasumsikan keadaan tertentu dan jika perhitungan dilakukan di lebih dari satu tempat, maka negara tersebut juga harus didistribusikan.

Makalah yang berpengaruh ( Paxos , dan yang lebih baru-baru ini Raft ) dalam domain ini diterbitkan setelah makalah yang Anda kutip. Keduanya membahas masalah konsensus di hadapan beberapa kegagalan.

Kesalahan Bizantium dapat dihindari dalam sistem terdistribusi menggunakan beberapa pendekatan.

Lihatlah entri Wikipedia di Byzantine Fault Tolerance .

diginoise
sumber
Hasil ketidakmungkinan FLP berlaku bahkan dalam pengaturan kegagalan paling dasar (crash) jadi saya tidak yakin apa gunanya paragraf tentang menghindari kegagalan Bizantium. Perhatikan bahwa jika kita tidak mengalami kegagalan maka konsensus agak mudah: satu proses tetap menyiarkan nilainya dan setiap proses menentukan nilainya segera setelah diterima.
Kaveh