Consensus dalam Sistem Terdistribusi

Consensus merupakan penentuan nilai. Penentuan ini dilakukan dari berbagai entitas atau dalam kasus ini dari berbagai proses. Setiap proses memiliki nilai yang ia calonkan.  Pada akhirnya diharapkan semua proses menentukan nilai yang sama dari kumpulan calon tersebut.

Consesnsus memiliki dua primitive: propose dan decide. Setiap proses memiliki nilai awal yang mereka ajukan untuk persetujuan bersama, melalui primitive propose.

Nilai yang diajukan hanya diketahui proses itu sendiri dan pengajuan bersifat lokal. Pengajuan ini memicu suatu kejadian broadcast sehingga semua proses bertukar nilai untuk pada akhirnya mencapai kesepakatan. Semua proses yang berjalan harus menentukan satu nilai kesepakatan melalui primitive decide. Nilai ini harus merupakan salah satu dari nilai yang diajukan.

Ada dua algoritma stop-fail: Algoritma pertama menggunakan langkah komunikasi yang sedikit dengan pesan yang banyak. Sedangkan yang kedua sebaliknya, pesannya sedikit namun langkah komunikasinya banyak.

Algoritma consensus yang pertama, Algoritma 5.1, yang dinamakan Flooding Consensus menggunakan abstraksi komunikasi broadcast usaha-terbaik (best-effort broadcast communication abstraction). Ide dari algoritma ini adalah sebagai berikut. Proses-proses yang ada mengeksekusi ronde-ronde secara sekuensial. Setiap proses mengelola himpunan nilai-nilai yang diajukan yang telah ia liat, dan himpunan ini akan terus augmentasikan dari ronde ke ronde. Pada setiap ronde, setiap proses menyebarkan himpunannya ke semua proses menggunakan abstraksi komunikasi broadcast usaha-terbaik. Dengan kata lain proses membanjiri system dengan himpunan proposal yang telah ia liat pada ronde sebelumnya. Ketika proses menerima himpunan proposal dari proses lain, himpunan tersebut akan digabung dengan himpunan miliknya. Sehingga pada setiap ronde, setiap proses mengkalkulasi union dari semua himpunan yang pernah ia terima.

 

Algoritma 5.2. disebut “Hierarchical Consensus” adalah alternative untuk menerapkan regular consensus. Algoritma ini menarik karena menggunakan pesan yang sedikit dibanding algoritma “Flooding Consensus” dan membiarkan satu proses untuk menentukan sebelum menukar pesan dengan proses yang lain (0-latency). Namun, untuk mencapai keputusan global, untuk setiap proses yang berjalan yang menentukan, algoritma membutuhkan langkah komunikasi N, bahkan dalam situasi tanpa failure. Algoritma 5.2 cukup jika consensus digunakan sebagai implementasi servis oleh himpunan proses server dimana klien cukup puas untuk mendapatkan nilai secepat mungkin, bahkan jika server-server belum menentukan nilai.

Selamat Membaca! Semangat bagi yang menempuh ujian

Sumber:

Introduction to Reliable Distributed Programming by Rachid Guerraoui dan Luís Rodrigues