Inilah Fault Tolerance dalam Sistem Terdistribusi

Assalamu‘alaikum wr. wb.

Hello guys! Jika sebelumnya sudah membahas tentang Konsistensi dan Replikasi, sekarang waktunya membahas tentang Fault Tolerance, yang merupakan Batas Toleransi Kesalahan dalam suatu Sistem.

FAULT TOLERANCE

Sumber Materi : CSIS.PACE.edu, Komputasi.Files.Wordpress.com (PDF), Fortinet.com, Geeksforgeeks.org, Blog.Sofwancoder.com, Imperva.com, Huzefril.com, Dremio.com, Users.CS.Duke.edu, ICS.UCI.edu (PDF), dan IA.PW.edu.pl (PDF)

A. Pengertian Fault Tolerance

Fault Tolerance (Processor and Memory)

Ketahanan Kesalahan atau Fault Tolerance merujuk pada kemampuan suatu sistem (komputer, jaringan, gugus awan, dll.) untuk terus beroperasi tanpa gangguan ketika satu atau lebih komponennya mengalami kegagalan.

Tujuan pembuatan sistem yang tahan kesalahan adalah untuk mencegah gangguan yang timbul dari satu titik kegagalan, memastikan ketersediaan tinggi dan kelangsungan bisnis dari aplikasi atau sistem yang sangat kritis.

Sistem yang Tahan Kesalahan menggunakan komponen cadangan yang secara otomatis menggantikan komponen yang mengalami kegagalan, memastikan tidak ada layanan yang hilang. Ini melibatkan :

• Sistem perangkat keras yang didukung oleh sistem identik atau setara. Sebagai contoh, server dapat dibuat tahan kesalahan dengan menggunakan server identik yang beroperasi secara paralel, dengan semua operasi yang dicerminkan ke server cadangan.
• Sistem perangkat lunak yang didukung oleh instansi perangkat lunak lain. Sebagai contoh, basis data dengan informasi pelanggan dapat terus direplikasi ke mesin lain. Jika basis data utama mengalami kegagalan, operasi dapat dialihkan secara otomatis ke basis data kedua.
• Sumber daya daya yang dibuat tahan kesalahan dengan menggunakan sumber daya alternatif. Sebagai contoh, banyak organisasi memiliki generator daya yang dapat mengambil alih jika pasokan listrik utama mengalami kegagalan.
• Dengan cara yang sama, setiap sistem atau komponen yang merupakan titik kegagalan tunggal dapat dibuat tahan kesalahan dengan menggunakan redundansi.

Fault Tolerance dapat memainkan peran dalam strategi pemulihan bencana. Sebagai contoh, sistem yang tahan kesalahan dengan komponen cadangan di awan dapat memulihkan sistem yang sangat penting dengan cepat, bahkan jika bencana alam atau bencana yang disebabkan manusia menghancurkan infrastruktur TI di lokasi.

B. Komponen Fault Tolerance

Manfaat kunci dari ketahanan kesalahan adalah untuk meminimalkan atau menghindari risiko sistem menjadi tidak tersedia karena kesalahan komponen. Hal ini terutama penting dalam sistem-sistem kritis yang diandalkan untuk menjamin keselamatan orang, seperti pengendalian lalu lintas udara, dan sistem yang melindungi serta mengamankan data kritis dan transaksi bernilai tinggi.

Komponen inti untuk meningkatkan ketahanan kesalahan melibatkan :

1. Diversitas

Jika pasokan listrik utama suatu sistem gagal, mungkin karena badai yang menyebabkan pemadaman listrik atau mempengaruhi pembangkit listrik, maka tidak akan mungkin untuk mengakses sumber listrik alternatif. Dalam kejadian ini, ketahanan kesalahan dapat diperoleh melalui diversitas, yang menyediakan listrik dari sumber-sumber seperti generator cadangan yang mengambil alih ketika kegagalan listrik utama terjadi.

Beberapa opsi ketahanan kesalahan yang beragam mengakibatkan cadangan tidak memiliki tingkat kapasitas yang sama dengan sumber utama. Hal ini mungkin, dalam beberapa kasus, memerlukan sistem untuk memastikan degradasi yang lancar sampai sumber daya listrik utama dipulihkan.

2. Redundansi

Sistem tahan kesalahan menggunakan redundansi untuk menghilangkan titik kegagalan tunggal. Sistem dilengkapi dengan satu atau lebih unit pasokan daya (PSU), yang tidak perlu memberi daya ke sistem ketika PSU utama berfungsi normal. Jika PSU utama mengalami kegagalan atau gangguan, dapat dihapus dari layanan dan digantikan oleh PSU cadangan, yang mengambil alih fungsi dan kinerja sistem.

Alternatifnya, Redundansi dapat diberlakukan pada tingkat sistem, yang berarti seluruh sistem komputer alternatif ada jika kegagalan terjadi.

3. Replikasi

Replikasi adalah pendekatan yang lebih kompleks untuk mencapai ketahanan kesalahan. Ini melibatkan penggunaan beberapa versi identik dari sistem dan subsistem dan memastikan bahwa fungsi mereka selalu memberikan hasil yang identik. Jika hasilnya tidak identik, maka prosedur demokratis digunakan untuk mengidentifikasi sistem yang rusak. Sebagai alternatif, dapat digunakan prosedur untuk memeriksa sistem yang menunjukkan hasil yang berbeda, yang menunjukkan bahwa sistem tersebut rusak.

Replikasi dapat terjadi pada tingkat komponen, yang melibatkan beberapa prosesor berjalan secara simultan, atau pada tingkat sistem, yang melibatkan sistem komputer identik yang berjalan secara simultan.

C. Jenis-jenis Kesalahan pada Fault Tolerance

Kegagalan merupakan suatu deviasi (simpangan) dari jalan yang telah ditetapkan (specified behavior)

• Misal, menekan pedal rem tidak menghentikan mobil kegagalan rem (dapat menjadi bencana besar!)
• Misal, membaca suatu sector disk tidak memperoleh konten kegagalan disk (bukan bencana cukup besar)

Banyak kegagalan disebabkan oleh perilaku spesifik yang salah :

• Ini biasanya terjadi ketika perancang gagal mengatasi skenario yang membuat sistem melakukan salah
• Ini terutama benar dalam sistem yang kompleks dengan banyak interaksi yang halus

Berikut ini merupakan beberapa Jenis dari Kesalahan/Kegagalan pada Fault Tolerance :

1. Crash Failure

Terjadi ketika suatu komponen atau proses dalam sistem tiba-tiba "crash" atau berhenti berfungsi tanpa memberikan peringatan.

Contoh : Layanan web yang berhenti berfungsi secara tiba-tiba tanpa peringatan.

2. Omission Failure (Receive/Send)

Kesalahan yang melibatkan kegagalan dalam mengirim atau menerima pesan atau sinyal di antara komponen sistem.

Server gagal merespon request yang masuk :

• Server gagal menerima message yang masuk
• Server gagal mengirimkan message

3. Timing Failure

Kesalahan yang terkait dengan keterlambatan atau ketidaktepatan dalam respons suatu komponen terhadap suatu peristiwa atau permintaan.

Contoh : Respons yang terlalu lambat dari server terhadap permintaan pengguna.

4. Response Failure (Value / State Transition)

Terkait dengan kesalahan dalam menghasilkan nilai respons yang benar atau dalam melakukan transisi keadaan yang diharapkan.

Respons server tidak tepat pada :

• Nilai responsnya salah
• Server menyimpang dari aliran kendali yang benar

5. Byzantine Failure

Merupakan jenis kegagalan yang kompleks dan dapat mencakup berbagai perilaku yang tidak sesuai atau bermasalah, termasuk menyebarkan informasi palsu atau memberikan respons yang bertentangan.

Contoh : Sebuah node dalam jaringan yang bersifat bermusuhan dan dapat menyebabkan konflik atau kekacauan dalam sistem.

6. Component Failure

Kesalahan ini terjadi ketika salah satu komponen fisik atau logis dalam sistem mengalami kegagalan. Ini bisa mencakup kegagalan perangkat keras (seperti hard drive atau CPU), kegagalan perangkat lunak, atau kegagalan jaringan.

7. Design Failure

Kesalahan ini terjadi ketika salah satu komponen fisik atau logis dalam sistem mengalami kegagalan. Ini bisa mencakup kegagalan perangkat keras (seperti hard drive atau CPU), kegagalan perangkat lunak, atau kegagalan jaringan.

8. System Failure

Ini adalah kegagalan yang mempengaruhi keseluruhan sistem. Meskipun sistem mungkin dirancang untuk toleran terhadap kegagalan, ada kemungkinan bahwa keseluruhan sistem bisa gagal.

9. Human Failure

Kegagalan manusia dapat mencakup kesalahan dalam pengoperasian sistem, kesalahan konfigurasi, atau bahkan kegagalan dalam merespon dengan benar terhadap tanda-tanda kegagalan.

10. Network Failure

Kesalahan ini melibatkan kegagalan koneksi atau komunikasi antara komponen sistem, bisa jadi karena gangguan jaringan atau masalah dengan protokol komunikasi.

11. Power Failure

Kegagalan catu daya dapat menyebabkan kegagalan sistem jika tidak ada langkah-langkah yang diambil untuk melindungi sistem dari pemadaman listrik atau penurunan tegangan yang signifikan.

12. Software Failure

Kesalahan perangkat lunak dapat terjadi dalam kode aplikasi, sistem operasi, atau komponen perangkat lunak lainnya. Kesalahan ini dapat memengaruhi kinerja sistem secara keseluruhan.

13. Data Failure

Kesalahan data bisa terjadi jika data yang dikelola oleh sistem rusak atau terkorupsi. Solusi backup dan pemulihan data perlu diterapkan untuk mengatasi jenis kegagalan ini.

14. Context Failure

Kesalahan ini terjadi ketika sistem gagal mengenali konteks atau kondisi tertentu yang memerlukan respons khusus. Ini bisa terjadi dalam sistem cerdas atau sistem yang bergantung pada konteks tertentu.

15. Security Failure

Kegagalan keamanan melibatkan pelanggaran keamanan sistem, seperti serangan siber atau akses yang tidak sah. Kesalahan ini dapat menyebabkan kebocoran data atau kerentanan keamanan lainnya.

Berikut ini adalah Jenis-jenis Kesalahan pada Fault Tolerance :

Teknik kunci untuk menutupi kegagalan adalah menggunakan redundancy :

D. Hal-hal Penting dalam Fault Tolerance

Tingkat Fault Tolerance (Toleransi Kesalahan) dalam suatu sistem merupakan indikator seberapa baik sistem dapat mengatasi dan tetap beroperasi ketika terjadi kesalahan atau kegagalan pada komponen-komponennya. Berikut adalah penjelasan tentang hal-hal penting dalam Fault Tolerance :

1. Peningkatan Keandalan (Increased Reliability)

Fault Tolerance bertujuan untuk meningkatkan keandalan sistem dengan mengurangi dampak kesalahan atau kegagalan komponen. Ini mencakup strategi seperti penggunaan redundansi dan pemulihan otomatis untuk menjaga ketersediaan sistem.

Contoh : Penggunaan replika data di berbagai node dalam sistem terdistribusi untuk memastikan data tetap dapat diakses bahkan jika satu node mengalami kegagalan.

2. Ketersediaan Tinggi (High Availability)

Tingkat Fault Tolerance yang tinggi berarti sistem memiliki ketersediaan tinggi, yaitu kemampuan untuk tetap beroperasi dan memberikan layanan meskipun terdapat kegagalan pada salah satu komponennya.

Contoh : Penggunaan mekanisme failover di sistem database atau server, di mana jika satu server mengalami kegagalan, lalu lintas dipindahkan secara otomatis ke server cadangan untuk menjaga ketersediaan layanan.

3. Integritas Data (Data Integrity)

Fault Tolerance juga melibatkan perlindungan terhadap integritas data. Sistem harus dirancang sedemikian rupa sehingga data tidak rusak atau mengalami kerusakan akibat kegagalan atau kesalahan.

Contoh : Penggunaan checksum atau metode verifikasi data lainnya untuk memastikan bahwa data yang disimpan atau dikirim tetap utuh.

4. Skalabilitas (Scalability)

Sistem yang fault-tolerant harus dapat berkembang sejalan dengan kebutuhan tanpa mengorbankan ketersediaan atau kinerja. Skalabilitas menjadi penting untuk menangani beban yang semakin besar.

Contoh : Desain sistem terdistribusi yang dapat menambahkan lebih banyak node saat diperlukan untuk menangani lonjakan trafik atau kapasitas data yang lebih besar.

5. Pemulihan Bencana (Disaster Recovery)

Untuk situasi yang lebih ekstrem, seperti bencana alam atau kejadian yang menyebabkan kerusakan besar pada suatu pusat data, fault tolerance juga melibatkan kemampuan untuk memulihkan operasi dari pusat data cadangan atau lokasi alternatif.

Contoh : Penyimpanan backup data di pusat data geografis yang berbeda untuk memastikan bahwa data dapat dipulihkan setelah bencana yang merusak satu lokasi.

E. Fase/Tahapan dalam Fault Tolerance

Fase/Tahapan dalam Fault Tolerance

Untuk mengimplementasikan Teknik Ketahanan Kesalahan (Fault Tolerance) dalam Sistem Terdistribusi, perlu mempertimbangkan desain, konfigurasi, dan aplikasi terkait. Berikut adalah fase-fase yang dilakukan untuk ketahanan kesalahan dalam sistem terdistribusi.

1. Deteksi Kesalahan (Fault Detection)

Deteksi Kesalahan adalah fase pertama di mana sistem terus dipantau. Hasilnya dibandingkan dengan output yang diharapkan. Selama pemantauan, jika teridentifikasi kesalahan, mereka segera dilaporkan. Kesalahan dapat terjadi karena berbagai alasan seperti kegagalan perangkat keras, kegagalan jaringan, dan masalah perangkat lunak. Tujuan utama dari fase pertama ini adalah mendeteksi kesalahan sesegera mungkin sehingga pekerjaan yang diberikan tidak tertunda.

2. Diagnosis Kesalahan (Fault Diagnosis)

Diagnosis kesalahan adalah proses di mana kesalahan yang diidentifikasi pada fase pertama akan didiagnosis dengan benar untuk mendapatkan penyebab akar dan sifat mungkin dari kesalahan tersebut. Diagnosis kesalahan dapat dilakukan secara manual oleh administrator atau menggunakan Teknik otomatisasi untuk memecahkan kesalahan dan melaksanakan tugas yang diberikan.

3. Generasi Bukti (Evidence Generation)

Generasi bukti didefinisikan sebagai proses di mana laporan kesalahan disusun berdasarkan diagnosis yang dilakukan pada fase sebelumnya. Laporan ini berisi rincian penyebab kesalahan, sifat kesalahan, solusi yang dapat digunakan untuk memperbaiki, dan alternatif serta pencegahan lain yang perlu dipertimbangkan.

4. Penilaian (Assessment)

Penilaian adalah proses di mana kerusakan yang disebabkan oleh kesalahan dianalisis. Hal ini dapat ditentukan dengan bantuan pesan yang dilewatkan dari komponen yang mengalami kesalahan. Berdasarkan penilaian, keputusan lebih lanjut dibuat.

5. Pemulihan (Recovery)

Pemulihan adalah proses di mana tujuannya adalah membuat sistem bebas kesalahan. Ini adalah langkah untuk membuat sistem bebas kesalahan dan mengembalikannya ke pemulihan ke depan dan pemulihan cadangan. Beberapa teknik pemulihan umum seperti rekonfigurasi dan resinkronisasi dapat digunakan.

F. Elemen/Unsur dalam Fault Tolerance

Sistem yang toleran terhadap kesalahan juga menggunakan komponen cadangan, yang secara otomatis menggantikan komponen yang gagal untuk mencegah kehilangan layanan. Komponen cadangan ini meliputi :

1. Toleransi Kesalahan Perangkat Keras (Hardware Fault Tolerance)

Toleransi Kesalahan Perangkat Keras melibatkan penyediaan rencana cadangan untuk perangkat keras seperti memori, hard disk, CPU, dan perangkat keras lainnya. Toleransi Kesalahan Perangkat Keras adalah jenis toleransi kesalahan yang tidak memeriksa kesalahan dan kesalahan waktu eksekusi tetapi hanya dapat menyediakan cadangan perangkat keras. Dua pendekatan yang berbeda yang digunakan dalam Toleransi Kesalahan Perangkat Keras adalah penyamaran kesalahan dan pemulihan dinamis.

2. Toleransi Kesalahan Perangkat Lunak (Software Fault Tolerance)

Toleransi Kesalahan Perangkat Lunak adalah jenis toleransi kesalahan di mana perangkat lunak khusus digunakan untuk mendeteksi keluaran yang tidak valid, waktu eksekusi, dan kesalahan pemrograman. Toleransi Kesalahan Perangkat Lunak menggunakan metode statis dan dinamis untuk mendeteksi dan memberikan solusi. Toleransi Kesalahan Perangkat Lunak juga terdiri dari poin data tambahan seperti pemulihan mundur dan titik kontrol.

3. Toleransi Kesalahan Sistem (System Fault Tolerance)

Toleransi Kesalahan Sistem adalah jenis toleransi kesalahan yang mencakup seluruh sistem. Ini memiliki keunggulan bahwa tidak hanya menyimpan titik-titik kontrol tetapi juga blok memori, dan titik kontrol program serta mendeteksi kesalahan dalam aplikasi secara otomatis. Jika sistem mengalami jenis kesalahan atau kesalahan apa pun, itu memberikan mekanisme yang diperlukan untuk solusinya. Dengan demikian, toleransi kesalahan sistem dapat diandalkan dan efisien.

G. Process Resilience dalam Fault Tolerance

Grup Proses : Lindungi diri Anda dari proses yang salah dengan mereplikasi dan mendistribusikan komputasi dalam grup.

1. Grup Datar

Baik untuk toleransi kesalahan karena pertukaran informasi segera terjadi dengan semua anggota grup. Mungkin membebankan lebih banyak overhead karena kendali didistribusikan sepenuhnya (sulit diterapkan).

2. Grup Hierarki

Semua komunikasi melalui satu koordinator ⇒ tidak terlalu toleran terhadap kesalahan dan terukur, namun relatif mudah diterapkan.

Di bawah ini adalah beberapa strategi yang dapat dikategorikan sebagai upaya meningkatkan ketahanan pada kelompok atau proses (group/process resilience) dalam konteks Fault Tolerance :

1. Redundansi

Deskripsi: Menyediakan salinan cadangan dari komponen atau layanan tertentu sehingga jika satu komponen gagal, yang lain dapat mengambil alih.

Contoh: Redundansi server atau replikasi data untuk menangani kegagalan.

2. Load Balancing

Deskripsi: Mendistribusikan beban kerja secara merata di antara berbagai komponen atau server untuk mencegah satu komponen tertentu menjadi bottleneck.

Contoh: Distribusi lalu lintas web di antara beberapa server untuk mengoptimalkan kinerja.

3. Auto-Scaling

Deskripsi: Menyesuaikan otomatis kapasitas sistem berdasarkan permintaan atau beban kerja, sehingga sistem dapat menanggapi fluktuasi lalu lintas.

Contoh: Penambahan atau pengurangan instance server secara otomatis berdasarkan beban kerja.

4. Failover

Deskripsi: Pemindahan otomatis operasi dari satu komponen atau server ke yang lain jika yang pertama mengalami kegagalan.

Contoh: Sistem basis data yang beralih ke salinan cadangan jika server utama mengalami kegagalan.

5. State Preservation

Deskripsi: Mempertahankan keadaan (state) kritis dari sistem atau komponen tertentu sehingga, dalam kasus kegagalan, sistem dapat memulihkan operasi dari titik terakhir yang diketahui.

Contoh: Mereplikasi dan mempertahankan status sesi pengguna pada server.

6. Distributed Transactions

Deskripsi: Memastikan keberlanjutan transaksi di antara beberapa node atau komponen sistem terdistribusi.

Contoh: Penyimpanan data terdistribusi yang menggunakan transaksi untuk menjaga konsistensi data.

7. Health Monitoring and Reporting

Deskripsi: Pemantauan kesehatan sistem secara terus-menerus dan pelaporan ke sistem manajemen kesalahan atau administrator ketika ada anomali.

Contoh: Pemantauan tingkat kinerja server dan pelaporan ke sistem manajemen jika beban melebihi ambang batas.

8. Graceful Degradation

Deskripsi: Menjalankan sistem dengan kapabilitas yang lebih rendah atau fungsionalitas yang berkurang jika terjadi kegagalan, untuk memastikan kelangsungan operasi yang lebih lanjut.

Contoh: Situs web yang menampilkan versi sederhana atau "mode darurat" jika server utama tidak dapat diakses.

CONSENSUS PROBLEM

Sumber Materi : CSIS.PACE.edu, Komputasi.Files.Wordpress.com (PDF), CS.UIC.edu (PDF), W3.cs.Jmu.edu, dan Baeldung.com

A. Byzantine General Problem

Sumber : Thecode11.com, Baeldung.com, dan Educative.io

Ketika sebuah grup dapat menutupi k kegagalan anggota secara bersamaan, maka disebut sebagai k-fault toleran (k disebut derajat toleransi kesalahan).

Jika kita berasumsi bahwa semua anggota identik, dan memproses semua masukan dalam urutan yang sama.

Seberapa besar kelompok yang toleran terhadap kesalahan k?

• Asumsikan semantik kerusakan/kegagalan kinerja ⇒ total k+1 anggota diperlukan untuk bertahan dari kegagalan k anggota.
• Mengasumsikan semantik kegagalan sewenang-wenang, dan keluaran kelompok ditentukan dengan pemungutan suara ⇒ total 2k + 1 anggota diperlukan untuk bertahan dari kegagalan k anggota.

Asumsi : Anggota grup tidak identik, yaitu kita memiliki perhitungan terdistribusi.

Masalah : Anggota kelompok yang tidak salah harus mencapai kesepakatan mengenai nilai yang sama.

Dengan asumsi semantik kegagalan yang sewenang-wenang, kita memerlukan 3k + 1 anggota grup untuk bertahan dari serangan k anggota yang salah.

Kami mencoba untuk mencapai suara mayoritas di antara kelompok loyalis, dengan adanya k pengkhianat ⇒ kami membutuhkan 2k +1 loyalis. Hal ini juga dikenal sebagai Kegagalan Bizantium (Byzantine Failures).

1. Konsensus Dalam Sistem yang Salah

Mencapai konsensus dalam sistem terdistribusi hanya dimungkinkan dalam keadaan berikut :

2. Masalah Jendral Bizantium (Byzantine Generals Problem)

Asumsi Lamport :

• Terdapat n proses (atau jenderal)
• Setiap proses i akan mengirimkan suatu value vi (yaitu “attack” atau “wait” atau sesuatu yang lain) ke setiap proses lainnya
• Ada paling banyak m proses yang gagal (faulty atau traitors)
• Setiap proses akan membangun suatu vector V dengan panjang n
• Jika proses i non-faulty, V[i] = vi
• Jika tidak, V[i] tidak didefinisikan

Kasus I : n = 4 dan m = 1

Kasus II : n = 3 dan m = 1

Kesimpulan :

Lamport et al. (1982) telah membuktikan bahwa di dalam suatu system dengan m proses yang gagal, suatu kesepakatan (agreement) dapat dicapai hanya jika 2m+1 proses yang berfungsi dengan benar hadir, sehingga total terdapat 3m+1

• BGP (n, m) dapat dipecahkan iff n ≥ (3m + 1)
• Dengan kata lain, suatu konsensus hanya mungkin dicapai jika masih terdapat lebih dari dua-per-tiga (2/3) proses bekerja dengan benar.

B. Praktik Byzantine Fault Tolerance (PBFT)

Dengan mempertimbangkan bahwa konsensus dapat dibuktikan tidak mungkin hadir dalam kondisi tertentu, layak untuk mempertimbangkan tingkat layanan yang dapat diandalkan yang dapat dicapai oleh proses dalam sistem terdistribusi. Artinya, kita dapat bertanya apakah mungkin untuk mengumpulkan informasi yang cukup andal untuk mencapai jawaban yang mungkin benar. Dengan menerapkan Algoritma Practical Byzantine Fault Tolerance (PBFT), dimungkinkan untuk replikasi keadaan yang andal dan efisien, selama sistem mempertahankan properti bahwa kurang dari 1/3 dari proses gagal. Perlu dicatat bahwa sistem tidak berusaha untuk mencapai konsensus—yang akan memerlukan semua proses yang benar untuk mencapai keputusan yang sama—tetapi untuk konsistensi yang cukup di antara cukup banyak respons untuk memberikan layanan yang dapat digunakan.

Reliable Service dengan Practical Byzantine Fault Tolerance (PBFT)

Dalam PBFT, seorang klien menghubungi proses utama yang ditunjuk yang bertanggung jawab atas data yang diminta. Proses utama diasumsikan benar dalam kasus normal, seperti yang ditunjukkan pada Gambar di atas. Kemudian, proses utama akan meneruskan permintaan ke beberapa replika yang seharusnya juga memiliki data yang diminta. Begitu klien menerima respons dari cukup banyak proses (termasuk proses utama dan replika), klien menganggap respons mayoritas sebagai benar.

Gambar di atas menunjukkan tahapan pertukaran pesan dalam PBFT. Ketika proses utama menerima permintaan, itu memasuki fase pre-prepare, memberi tahu replika tentang permintaan yang akan datang. Selama fase prepare, semua replika yang tidak rusak mengirimkan pesan yang mengakui permintaan ke semua replika lain dan ke proses utama. Begitu proses utama dan replika telah menerima cukup banyak pesan prepare, sistem kemudian memasuki fase commit, ketika proses utama mengirimkan permintaan sebenarnya ke replika-replika. Klien menerima hasil setelah menerima respons.

PBFT memiliki beberapa elemen kunci yang memungkinkannya memberikan layanan yang andal. Pertama, semua pesan ditandatangani secara kriptografis untuk mencegah pemalsuan; layanan yang rusak atau jahat tidak dapat menyuntikkan pesan palsu yang tampak berasal dari proses yang benar. Kedua, pesan pre-prepare dan prepare mencakup informasi urutan yang menciptakan total pengurutan pada permintaan. Ketika seorang utama menerima permintaan dari seorang klien, itu akan mencoba memproses permintaan tersebut sebelum permintaan apa pun yang datang kemudian. Secara khusus, utama tidak akan mengirimkan pesan pre-prepare untuk permintaan yang lebih baru sampai permintaan saat ini telah diproses. Ketiga, pesan-pesan mencakup cap waktu yang menempatkan durasi terbatas pada berapa lama permintaan dapat tertunda; jika replika-replika membutuhkan waktu terlalu lama untuk merespons dengan pesan prepare, utama akan meninggalkan permintaan tersebut dan tidak akan mengirimkan pesan commit.

Akhirnya, utama memerlukan sejumlah proses ambang yang harus merespons pada setiap tahap; dengan asumsi sistem menjamin f ≤ (n−1)/3 replika rusak (yaitu, sistem memenuhi persyaratan bahwa paling banyak 1/3 dari proses gagal pada setiap saat tertentu), maka diperlukan f pesan prepare untuk masuk ke tahap commit, dan klien akan memerlukan f+1 respons dengan hasil yang sama. Persyaratan ini sesuai dengan asumsi perilaku sistem. Jika 1/3 dari proses sistem mengalami kegagalan, maka 2/3 adalah benar dan semuanya akan setuju dengan nilai yang sama. Begitu klien dan/atau utama menerima lebih dari 1/3 respons yang cocok, setidaknya satu dari respons ini berasal dari simpul yang benar, dan respons tersebut mungkin dapat diandalkan.

PBFT dan pendekatan serupa secara rutin digunakan dalam berbagai pengaturan untuk menciptakan layanan yang andal dalam pengaturan yang tidak dapat diprediksi dan asinkron. Sebagai contoh, algoritma toleransi kesalahan Byzantine digunakan dalam aplikasi penyedia penyimpanan awan berbasis Internet, serta sistem pesawat yang memerlukan perilaku kritis keamanan real-time. PBFT tidak dapat menjamin konsensus, mengingat keterbatasan yang telah terbukti ketika kegagalan Byzantine dapat terjadi. Namun, PBFT dapat menyediakan tingkat layanan yang cukup dapat diandalkan untuk sistem, selama ada batasan pada jumlah proses yang dapat gagal.

C. Batasan Konsensus (Limits on Consensus)

Masalah Jenderal Byzantine menyoroti hambatan utama untuk mencapai konsensus dalam sistem terdistribusi: proses yang berperilaku buruk dapat mencegah fungsi yang benar dari proses lainnya. Selain itu, karena proses yang benar tidak dapat memiliki informasi yang sempurna tentang sisa sistem, satu atau lebih proses dapat muncul ke bagian yang berbeda dari sistem sebagai benar dan gagal pada saat yang bersamaan. Untuk lebih tepatnya, kegagalan Byzantine (juga disebut kesalahan Byzantine) terjadi ketika satu proses muncul sebagai kegagalan bagi beberapa proses yang benar, sementara juga muncul benar bagi proses lainnya; dalam kegagalan Byzantine, proses yang berbeda memiliki akses ke observasi yang berbeda dan konflik, dan tidak dapat menentukan informasi mana yang dapat diandalkan. Oleh karena itu, sistem tidak dapat menentukan bagaimana merespons informasi dari proses—yang mungkin tidak dapat diandalkan atau bermasalah.

Penelitian tentang masalah jenderal Byzantine telah menetapkan batasan teoretis yang signifikan pada konsensus dalam sistem terdistribusi. Jika pesan tidak dapat diautentikasi dan lebih dari 1/3 dari proses gagal, maka akan tidak mungkin bagi proses yang benar dan tidak bermasalah untuk mencapai konsensus dengan protokol apa pun. Untuk mengilustrasikan wawasan ini, pertimbangkan skenario yang dijelaskan sebelumnya berdasarkan pada Gambar Permasalahan Jendral Byzantine. Anggaplah bahwa letnan kiri adalah yang benar dan menerima pesan X=attack dari komandan. Dalam tahap konfirmasi protokol, letnan kiri menerima pesan bahwa "C berkata Mundur" dari letnan kanan. Letnan kiri adalah proses yang benar, tetapi tidak dapat diakhiri karena tidak dapat memutuskan tindakan mana yang merupakan pilihan yang benar. Penelitian lebih lanjut menunjukkan bahwa wawasan ini dapat digeneralisasikan untuk sistem apa pun dengan 1/3 dari proses yang gagal, misalnya jika ada 4 letnan pengkhianat dalam pasukan dengan 10 jenderal.

Jika sistem dapat menjamin bahwa kurang dari 1/3 dari proses gagal, konsensus masih mungkin dalam beberapa skenario. Untuk mengilustrasikan ini secara informal, anggaplah bahwa ada letnan ketiga dalam skenario dari Gambar Permasalahan Jendral Byzantine, dan paling banyak satu dari jenderal adalah pengkhianat. Jika komandan setia dan memerintahkan serangan, maka setiap letnan setia akan menerima perintah untuk menyerang bersama dengan setidaknya satu konfirmasi dari perintah tersebut; jika salah satu letnan menyatakan "C berkata Mundur," letnan lainnya dapat menentukan jenderal mana yang menjadi pengkhianat dengan melihat mayoritas.

Konsensus Mungkin Sekalipun Proses yang Gagal adalah Pemimpinnya

Namun, pertimbangkan kasus di mana komandan adalah seorang pengkhianat dan tiga letnan setia. Kemudian dua letnan menerima pesan untuk menyerang dan satu untuk mundur (atau sebaliknya), yang menyebabkan pertukaran pesan seperti yang ditunjukkan dalam Gambar 9.7.2. Karena letnan semuanya setia, mereka melaporkan apa yang mereka terima sebagai perintah dengan akurat. Letnan 1 dan 2 keduanya menerima tiga pesan: "Serang" (dari C), "C berkata Serang" (dari yang lain), dan "C berkata Mundur" (dari Letnan 3). Letnan 3 menerima "Mundur" dari C bersama dengan dua salinan "C berkata Serang" dari letnan lainnya. Letnan dapat mencapai konsensus lagi dengan melihat pesanan mana yang ada dalam mayoritas. Menariknya, perhatikan bahwa letnan 1 dan 2 tidak dapat menentukan proses mana yang gagal (pesan akan sama jika letnan 3 adalah jenderal yang tidak setia) tetapi mereka masih dapat mencapai konsensus.

Ada nuansa yang perlu ditambahkan pada kesimpulan ini, meskipun. Masalah jenderal Byzantine, seperti yang dijelaskan di atas, secara implisit mengasumsikan penggunaan komunikasi sinkron. Artinya, komandan mengeluarkan perintah "Lakukan X" dan "Lakukan Y" pada suatu waktu, dan para letnan bertukar pesan konfirmasi dalam kerangka waktu tertentu setelah itu. Namun, dalam lingkungan asinkron, dampak kegagalan jauh lebih buruk. Tanpa batas waktu pada tanggapan, proses dapat merespons pesan sebelumnya kapan saja di masa depan. Dengan demikian, ketika seorang letnan menerima pesan "C berkata serang," letnan tersebut tidak dapat menentukan apakah pesan itu sebagai respons terhadap perintah saat ini atau perintah dari tahun yang lalu. Ketika komunikasi asinkron terlibat, tidak mungkin bagi protokol manapun untuk menjamin bahwa konsensus dapat dicapai jika ada bahkan satu node yang gagal. Secara praktis, ada probabilitas non-nol bahwa proses dapat mencapai kesepakatan, tetapi begitu satu node gagal, tidak ada jaminan bahwa konsensus mungkin.

D. HotStuff Consensus Protocol

HotStuff adalah protokol replikasi toleran kesalahan Byzantine berbasis pemimpin lainnya. Ini diusulkan oleh penelitian VMware dalam makalah mereka, pada Tahun 2018. Ini sangat mirip dengan pBFT dalam lingkungan di mana ia beroperasi dan tujuan yang dilayani. Namun, ia mencoba untuk memperbaiki kekurangan PBFT, terutama dengan komunikasi peer-to-peer yang kompleks dan proses perubahan pandangan untuk pemilihan pemimpin.

PBFT melakukan dua putaran pertukaran pesan peer-to-peer untuk mencapai konsensus. HotStuff mengusulkan untuk menggantinya dengan semua pesan mengalir melalui pemimpin. Selain itu, PBFT memiliki proses perubahan pandangan yang terpisah. HotStuff mengusulkan untuk menyederhanakan ini dengan menggabungkan proses perubahan pandangan dengan proses normal. Perubahan ini menghasilkan fase-fase berbeda dalam putaran konsensus HotStuff :

Protokol Konsensus HotStuff

Algoritma ini dimulai dengan pemimpin mengumpulkan pesan "pandangan baru / new view" dari cukup sekunder. Kemudian, itu memulai pandangan baru dan mengirim pesan "siap" ke node lain. Setelah menerima suara "siap", pemimpin membuat dan mengirimkan pesan "pra-komit" ke semua node. Setelah menerima suara "pra-komit/pre-commit", pemimpin membuat dan mengirimkan pesan "komit/commit".

Akhirnya, setelah menerima cukup suara "komit/commit", pemimpin membuat dan mengirimkan pesan "putuskan" ke semua node. Setelah menerima pesan "putuskan/decide", sekunder menjalankan transisi status. Sekarang, HotStuff juga menambahkan perbaikan lain, seperti tanda tangan ambang batas dan pipelining fase-fase konsensus. Namun, masih memiliki keterbatasan dalam skala secara sewenang-wenang.

RELIABLE COMMUNICATION

Sumber Materi : CSIS.PACE.edu, Users.cs.duke.edu (PDF), Medium.com (@fairday), Blog.Bytebytego.com, Ivypanda.com, News.MIT.edu, Peter-o.Medium.com, dan LinkedIn.com (Pulse - adipan18)

Bayangkan ketika sedang berlibur, Anda bertemu dengan seseorang istimewa yang juga menikmati hal-hal yang sama. Anda menikmati kebersamaan satu sama lain, sehingga Anda memutuskan untuk tetap berhubungan ketika kembali ke rumah masing-masing. Anda memutuskan bahwa daripada hanya menggunakan telepon, Anda ingin memiliki interaksi yang dinamis untuk menjaga kehangatan. Anda berdua memutuskan untuk chatting di WhatsApp, kadang-kadang melakukan panggilan video melalui Facetime, dan ketika hal-hal penting perlu dilakukan, Anda berdua mengirim Email dengan lampiran. Semua aktivitas ini berfungsi di bawah jaringan terdistribusi yang terdiri dari komputer fisik, mesin virtual, dan protokol yang dapat diprogram. Jadi, bagaimana Anda bisa melakukan semua ini dalam hitungan milidetik ketika berada di rumah di Springfield, Michigan, jauh dari pasangan Anda di Praha, Republik Ceko?

Berkat jaringan komunikasi terdistribusi yang mengirim pesan dalam bentuk pulsa eklektik, didedikasikan sebagai byte data melalui kabel yang tersebar di seluruh dunia. Tetapi dalam hal ini, komunikasi Anda dipindahkan dari rumah Anda di Springfield, Michigan ke Praha, Republik Ceko hampir secara real-time. Jaringan komunikasi terdistribusi ini juga dijelaskan sebagai Sistem Terdistribusi.

Sebuah Sistem Terdistribusi mengomunikasikan pesan yang dikirim melalui jaringan node switching ke sebuah titik akhir. Node-node tersebut adalah komputer alih-alih telepon dalam hal ini, dikendalikan oleh switch sehingga cukup cerdas untuk memutuskan rute terbaik untuk mengirim setiap pesan.

Dalam Sistem Terdistribusi, banyak node dan koneksi menciptakan redundansi sehingga pesan dapat tiba melalui banyak jalur yang berbeda. Pesan dibagi menjadi blok-blok dengan panjang yang seragam untuk membuat transmisi lebih sederhana dan efisien. Ide dari penggantian blok pesan ini juga disebut sebagai penggantian paket, adalah desain dasar dari jaringan yang dijelaskan sebagai Internet.

Ketika Anda menghubungi layanan web modern seperti Google atau WhatsApp, Anda tidak hanya berinteraksi dengan satu mesin, di balik layar terdapat layanan kompleks yang dibangun dari koleksi mesin yang besar, masing-masing berkolaborasi untuk menyediakan layanan tertentu dari situs atau aplikasi tersebut.

Sebuah sistem terdistribusi adalah kumpulan mesin fisik yang berkomunikasi melalui tautan jaringan, terdiri dari proses perangkat lunak yang berkomunikasi melalui mekanisme komunikasi antar-proses (IPC) seperti HTTP. Dari perspektif implementasi, sebuah sistem terdistribusi adalah serangkaian komponen yang longgar terkait yang dapat diterapkan dan ditingkatkan secara independen yang disebut layanan.

Sebuah layanan mengimplementasikan satu bagian tertentu dari kapabilitas keseluruhan sistem. Antarmuka layanan digunakan untuk berkomunikasi dengan dunia luar.

Antarmuka "inbound" mendefinisikan operasi yang ditawarkan oleh layanan kepada klien-kliennya. Sebaliknya, antarmuka "outbound" mendefinisikan operasi yang layanan gunakan untuk berkomunikasi dengan layanan eksternal, seperti penyimpanan data, layanan pesan, dan banyak lainnya.

Sebuah adapter inbound adalah bagian dari Antarmuka Pemrograman Aplikasi (API) perangkat; itu menangani permintaan yang diterima dari mekanisme IPC, seperti HTTP, dengan memanggil operasi komunikasi antar proses melalui jaringan, yang disebut inter-process communication (IPC).

Protokol jaringan disusun dalam bentuk tumpukan, di mana setiap lapisan dibangun di atas abstraksi yang diberikan oleh lapisan di bawahnya. Lapisan yang lebih rendah lebih dekat dengan perangkat keras. Ketika suatu proses mengirim data ke proses lain melalui jaringan, data tersebut bergerak melalui tumpukan dari lapisan atas ke lapisan bawah dan sebaliknya di ujung lain.

Sejauh ini berkonsentrasi pada ketahanan proses (dengan menggunakan kelompok proses). Bagaimana dengan saluran komunikasi yang andal?

Deteksi kesalahan :

• Pembingkaian paket untuk memungkinkan deteksi kesalahan bit,
• Penggunaan penomoran bingkai untuk mendeteksi kehilangan paket.

Koreksi kesalahan :

• Tambahkan banyak redundansi sehingga paket yang rusak dapat dikoreksi secara otomatis,
• Minta pengiriman ulang paket yang hilang, atau N paket terakhir. Sebagian besar pekerjaan ini mengasumsikan komunikasi titik ke titik.

A. Reliable Communication dan Layanan dalam Layanan Model Client/Server

Struktur sistem terdistribusi: jaringan, penamaan dan addressing, klien dan server, permintaan/tanggapan (Web/HTTP) dan Remote Procedure Call (RPC), layanan multi-tier, mega-layanan geografis. Pengiriman pesan, model kegagalan, dan masalah partisi jaringan. Status dan lapisan penyimpanan data.

1. Layanan Node dan Jaringan

Dari mikro-layanan hingga mega-layanan; layanan multi-tier dan tumpukan layanan. Masalah skala dan ketahanan. Model kegagalan (fail-stop vs. Byzantine) dan pertahanan. Status dan pemulihan. Otoritas, kontrol, dan kepercayaan. Contoh: layanan web dan Jaringan Distribusi Konten (CDN).

2. Internet sebagai Sistem Terdistribusi

Tumpukan Jaringan: pesan dan aliran, soket, komunikasi yang dapat diandalkan dengan Transmission Control Protocol (TCP). IP-LAN klasik sebagai contoh penamaan/alamat: Dynamic Host Configuration Protocol (DHCP), Address Resolution Protocol (ARP), peran siaran, alokasi dan sewa alamat, ARP caching, ketinggalan cache, dan Time To Live (TTL).

3. Remote Procedure Call (RPC)

Klien, server, port, dan koneksi. Model permintaan-balasan dan antarmuka server (API). Memanggil metode server dengan RPC. Stubs API dan marshalling. Birrell-Nelson RPC klasik: pengiriman ulang, pengakuan, duplikat dan penekanan, cache balasan dan semantik At-Most-Once, interaksi RPC dengan utas dan konkurensi. Contoh aplikasi: toko nilai kunci (DSLabs Lab1). Bacaan: OSTEP, Birrell-Nelson.

4. Penyimpanan Jaringan Network File System (NFS)

Tinjauan abstraksi sistem file: ruang nama hierarki, direktori, file/inode, sistem file virtual (VFS) dalam kernel OS. NFS sebagai layanan RPC: RPC berbasis objek dan pegangan file NFS. Kegagalan dan pemulihan pada NFS klasik: operasi idempoten dan "statelessness", implikasi dari model stateless. Mendeteksi kegagalan sesi di NFSv3: penulisan asinkron yang dapat diandalkan dan operasi commit. Bacaan: OSTEP, NFS.

B. Reliable Group Communication

Mengingat betapa pentingnya ketahanan proses melalui replikasi, tidak mengherankan bahwa layanan multicast yang dapat diandalkan juga penting. Layanan semacam itu menjamin bahwa pesan dikirimkan ke semua anggota dalam suatu kelompok proses. Sayangnya, multicast yang dapat diandalkan ternyata cukup sulit. Pada bagian ini, kita akan melihat lebih dekat masalah yang terlibat dalam pengiriman pesan secara dapat diandalkan ke sebuah kelompok proses.

1. Skema Dasar Multicast yang Dapat Diandalkan (Basic Reliable-Multicasting Schemes)

Meskipun sebagian besar lapisan transport menawarkan saluran point-to-point yang dapat diandalkan, mereka jarang menawarkan komunikasi yang dapat diandalkan kepada sekelompok proses. Yang terbaik yang dapat mereka tawarkan adalah membiarkan setiap proses menyiapkan koneksi point-to-point ke setiap proses lain yang ingin dia berkomunikasi. Secara jelas, organisasi seperti itu tidak efisien karena dapat menyia-nyiakan bandwidth jaringan. Meskipun demikian, jika jumlah proses kecil, mencapai keandalan melalui saluran point-to-point yang dapat diandalkan adalah solusi yang sederhana dan seringkali mudah.

Untuk melampaui kasus ini, kita perlu mendefinisikan dengan tepat apa itu multicast yang dapat diandalkan. Secara intuitif, ini berarti bahwa pesan yang dikirim ke sebuah kelompok proses harus diterima oleh setiap anggota dari kelompok tersebut. Namun, apa yang terjadi jika selama komunikasi sebuah proses bergabung dengan kelompok? Haruskah proses itu juga menerima pesan? Demikian pula, kita juga harus menentukan apa yang terjadi jika sebuah proses (pengirim) mengalami kegagalan selama komunikasi.

Untuk menangani situasi tersebut, perlu dibuat perbedaan antara komunikasi yang dapat diandalkan dalam keberadaan proses yang rusak, dan komunikasi yang dapat diandalkan ketika proses diasumsikan beroperasi dengan benar. Pada kasus pertama, multicast dianggap dapat diandalkan ketika dapat dijamin bahwa semua anggota kelompok yang tidak rusak menerima pesan. Bagian sulitnya adalah bahwa kesepakatan harus dicapai tentang seperti apa kelompok tersebut sebelum pesan dapat dikirimkan, ditambah dengan berbagai kendala penataan. Kita akan kembali membahas masalah ini ketika kita membahas multicasting atomik di bawah ini.

Situasinya menjadi lebih sederhana jika kita mengasumsikan bahwa ada kesepakatan tentang siapa yang menjadi anggota kelompok dan siapa yang bukan. Terutama, jika kita mengasumsikan bahwa proses tidak gagal, dan proses tidak bergabung atau meninggalkan kelompok selama komunikasi berlangsung, multicast yang dapat diandalkan hanya berarti bahwa setiap pesan harus dikirimkan kepada setiap anggota kelompok saat ini. Dalam kasus paling sederhana, tidak ada persyaratan bahwa semua anggota kelompok menerima pesan dalam urutan yang sama, tetapi terkadang fitur ini dibutuhkan.

Jenis multicast yang dapat diandalkan yang lebih lemah ini relatif mudah diimplementasikan, sekali lagi dengan syarat bahwa jumlah penerima terbatas. Pertimbangkan kasus di mana satu pengirim ingin melakukan multicast pesan ke beberapa penerima. Anggaplah bahwa sistem komunikasi yang mendasarinya hanya menawarkan multicast yang tidak dapat diandalkan, yang berarti bahwa pesan multicast mungkin hilang sebagian dan diterima oleh beberapa, tetapi tidak semua, penerima yang dimaksud.

Solusi sederhana ditunjukkan pada Gambar 8.9. Proses pengirim memberikan nomor urut kepada setiap pesan yang dia multicast. Kita asumsikan bahwa pesan diterima sesuai dengan urutan pengiriman. Dengan cara ini, mudah bagi penerima untuk mendeteksi bahwa ia melewatkan sebuah pesan. Setiap pesan multicast disimpan secara lokal dalam buffer riwayat di pengirim. Dengan asumsi penerima diketahui oleh pengirim, pengirim hanya menyimpan pesan dalam buffer riwayatnya sampai setiap penerima mengembalikan pengakuan. Jika seorang penerima mendeteksi bahwa ia melewatkan sebuah pesan, ia dapat mengembalikan pengakuan negatif, meminta pengirim untuk melakukan pengiriman ulang. Atau, pengirim dapat secara otomatis mengulang pesan ketika ia tidak menerima semua pengakuan dalam waktu tertentu.

Gambar 8.9. Solusi sederhana untuk multicast yang dapat diandalkan ketika semua penerima diketahui dan diasumsikan tidak mengalami kegagalan. (a) Pengiriman pesan. (b) Pelaporan umpan balik.

Gambar 8.9

Ada berbagai trade-off desain yang harus dibuat. Sebagai contoh, untuk mengurangi jumlah pesan yang dikembalikan ke pengirim, acknowledgment mungkin dapat disematkan (piggybacked) dengan pesan lain. Juga, pengiriman ulang pesan dapat dilakukan menggunakan komunikasi point-to-point ke setiap proses yang meminta, atau menggunakan satu pesan multicast yang dikirim ke semua proses. Survei menyeluruh dan rinci tentang total-order broadcasts dapat ditemukan di Defago et al. (2004).

2. Skalabilitas dalam Multicast yang Dapat Diandalkan (Scalability in Reliable Multicasting)

Masalah utama dengan skema multicast yang dapat diandalkan yang baru saja dijelaskan adalah bahwa itu tidak dapat mendukung jumlah penerima yang besar. Jika ada N penerima, pengirim harus bersiap menerima setidaknya N acknowledgment. Dengan banyak penerima, pengirim mungkin kebanjiran pesan umpan balik seperti itu, yang juga disebut sebagai implosi umpan balik. Selain itu, kita mungkin juga perlu memperhitungkan bahwa para penerima tersebar di seluruh jaringan area luas.

Salah satu solusi untuk masalah ini adalah dengan tidak membuat penerima mengakui penerimaan pesan. Sebaliknya, seorang penerima mengembalikan pesan umpan balik hanya untuk memberi tahu pengirim bahwa ia melewatkan sebuah pesan. Mengembalikan hanya acknowledgment negatif seperti itu dapat ditunjukkan secara umum lebih berskala [lihat, misalnya, Towsley et al. (1997)], tetapi tidak ada jaminan kuat bahwa implosi umpan balik tidak akan pernah terjadi.

Masalah lain dengan mengembalikan hanya acknowledgment negatif adalah bahwa pengirim, pada teorinya, akan terpaksa menyimpan pesan di buffer riwayatnya selamanya. Karena pengirim tidak pernah tahu apakah pesan telah dikirimkan dengan benar ke semua penerima, ia harus selalu bersiap untuk penerima yang meminta pengiriman ulang pesan lama. Secara praktis, pengirim akan menghapus pesan dari buffer riwayatnya setelah beberapa waktu berlalu untuk mencegah buffer dari overflow. Namun, menghapus pesan dilakukan dengan risiko permintaan pengiriman ulang tidak dihormati.

Ada beberapa proposal untuk multicast yang dapat diandalkan yang bersifat scalable. Perbandingan antara skema yang berbeda dapat ditemukan di Levine dan Garcia-Luna-Aceves (1998). Kami sekarang secara singkat membahas dua pendekatan yang sangat berbeda yang mewakili banyak solusi yang ada.

a. Kontrol Umpan Balik Non-Hierarkis (Nonhierarchical Feedback Control)

Isu kunci untuk solusi berskala dalam multicast yang dapat diandalkan adalah mengurangi jumlah pesan umpan balik yang dikembalikan ke pengirim. Model populer yang telah diterapkan pada beberapa aplikasi di area luas adalah feedback suppression. Skema ini mendasari protokol Scalable Reliable Multicasting (SRM) yang dikembangkan oleh Floyd et al. (1997) dan bekerja sebagai berikut.

Pertama, dalam SRM, penerima tidak pernah mengakui pengiriman sukses pesan multicast, tetapi sebaliknya, melaporkan hanya ketika mereka melewatkan sebuah pesan. Bagaimana kehilangan pesan terdeteksi dibiarkan pada aplikasi. Hanya acknowledgment negatif yang dikembalikan sebagai umpan balik. Setiap kali seorang penerima menyadari bahwa ia melewatkan sebuah pesan, ia melakukan multicast umpan baliknya ke seluruh kelompok.

Multicast umpan balik memungkinkan anggota kelompok lain untuk menekan umpan balik mereka sendiri. Misalkan beberapa penerima melewatkan pesan m. Masing-masing dari mereka perlu mengembalikan acknowledgment negatif ke pengirim, S, agar m dapat dikirimkan ulang. Namun, jika kita mengasumsikan bahwa pengiriman ulang selalu dilakukan multicast ke seluruh kelompok, cukup jika hanya satu permintaan pengiriman ulang yang mencapai S.

Untuk alasan ini, seorang penerima R yang tidak menerima pesan m menjadwalkan pesan umpan balik dengan beberapa penundaan acak. Artinya, permintaan pengiriman ulang tidak dikirimkan sampai beberapa waktu acak telah berlalu. Jika, dalam waktu tersebut, permintaan pengiriman ulang lainnya untuk m mencapai R, R akan menekan umpan baliknya sendiri, mengetahui bahwa m akan dikirimkan ulang segera. Dengan cara ini, pada dasarnya, hanya satu pesan umpan balik yang akan mencapai S, yang pada gilirannya kemudian mengirimkan kembali m. Skema ini ditunjukkan di Gambar 8.10.

Gambar 8.10

Penekanan penghambatan umpan balik telah terbukti berskala cukup baik, dan telah digunakan sebagai mekanisme dasar untuk sejumlah aplikasi Internet kolaboratif, seperti papan tulis bersama. Namun, pendekatan ini juga memunculkan sejumlah masalah serius. Pertama, memastikan bahwa hanya satu permintaan pengiriman ulang yang dikembalikan ke pengirim memerlukan penjadwalan yang cukup akurat dari pesan umpan balik di setiap penerima. Jika tidak, banyak penerima masih akan mengembalikan umpan balik mereka pada saat yang sama. Menetapkan timer dengan benar dalam kelompok proses yang tersebar di seluruh jaringan area luas tidak semudah itu.

Masalah lain adalah bahwa pengiriman umpan balik juga mengganggu proses-proses yang pesan telah berhasil dikirimkan kepadanya. Dengan kata lain, penerima lain terpaksa menerima dan memproses pesan yang tidak berguna bagi mereka. Satu-satunya solusi untuk masalah ini adalah membiarkan penerima yang tidak menerima pesan m bergabung dalam grup multicast terpisah untuk m, seperti yang dijelaskan dalam Kasera et al. (1997). Sayangnya, solusi ini memerlukan bahwa grup dapat dikelola dengan cara yang sangat efisien, yang sulit dicapai dalam sistem area luas. Pendekatan yang lebih baik adalah membiarkan penerima yang cenderung melewatkan pesan yang sama bermitra dan berbagi saluran multicast yang sama untuk pesan umpan balik dan pengiriman ulang. Detail tentang pendekatan ini dapat ditemukan di Liu et al. (1998).

Untuk meningkatkan Skalabilitas SRM, berguna untuk membiarkan penerima membantu dalam pemulihan lokal. Secara khusus, jika seorang penerima kepada pesan m telah berhasil dikirimkan, menerima permintaan pengiriman ulang, ia dapat memutuskan untuk melakukan multicast m bahkan sebelum permintaan pengiriman ulang mencapai pengirim asli. Detail lebih lanjut dapat ditemukan di Floyd et al. (1997) dan Liu et al. (1998).

b. Kontrol Umpan Balik Hierarkis (Hierarchical Feedback Control)

Penekanan umpan balik seperti yang baru saja dijelaskan pada dasarnya adalah solusi nonhierarki. Namun, mencapai skalabilitas untuk kelompok penerima yang sangat besar memerlukan adopsi pendekatan hirarkis. Pada dasarnya, solusi hirarkis untuk multicast yang dapat diandalkan bekerja seperti yang ditunjukkan di Gambar 8.11.

Gambar 8.11

Untuk menyederhanakan masalah, asumsikan hanya ada satu pengirim yang perlu melakukan multicast pesan ke kelompok penerima yang sangat besar. Kelompok penerima dibagi menjadi sejumlah subkelompok, yang kemudian diorganisir menjadi sebuah pohon. Subkelompok yang berisi pengirim membentuk akar dari pohon tersebut. Dalam setiap subkelompok, skema multicast yang dapat diandalkan yang berfungsi untuk kelompok kecil dapat digunakan.

Setiap subkelompok menunjuk koordinator lokal, yang bertanggung jawab atas penanganan permintaan pengiriman ulang dari penerima yang terdapat dalam subkelompoknya. Koordinator lokal akan memiliki buffer riwayatnya sendiri. Jika koordinator itu sendiri melewatkan pesan m, ia meminta koordinator subkelompok induk untuk mengirimkan kembali m. Dalam skema yang didasarkan pada acknowledgment, koordinator lokal mengirimkan acknowledgment ke induknya jika ia telah menerima pesan tersebut. Jika seorang koordinator telah menerima acknowledgment untuk pesan m dari semua anggota dalam subkelompoknya, serta dari anak-anaknya, ia dapat menghapus m dari buffer riwayatnya.

Masalah utama dengan solusi hirarkis adalah konstruksi pohonnya. Dalam banyak kasus, pohon perlu dibangun secara dinamis. Salah satu pendekatan adalah memanfaatkan pohon multicast dalam jaringan yang mendasarinya, jika ada. Pada dasarnya, pendekatan ini adalah untuk meningkatkan setiap router multicast dalam lapisan jaringan sedemikian rupa sehingga dapat bertindak sebagai koordinator lokal seperti yang baru saja dijelaskan. Namun, sebagai masalah praktis, adaptasi seperti itu pada jaringan komputer yang sudah ada tidak mudah dilakukan. Oleh karena itu, solusi multicast tingkat aplikasi seperti yang dibahas dalam Reliable Communication telah menjadi populer.

Sebagai kesimpulan, membangun skema multicast yang dapat diandalkan yang dapat berskala untuk sejumlah besar penerima yang tersebar di seluruh jaringan area luas adalah masalah yang sulit. Tidak ada solusi terbaik tunggal, dan setiap solusi memperkenalkan masalah baru.

3. Multicast Atomik

Mari sekarang kembali ke situasi di mana kita perlu mencapai multicast yang dapat diandalkan dalam keberadaan kegagalan proses. Secara khusus, yang sering dibutuhkan dalam sistem terdistribusi adalah jaminan bahwa suatu pesan dikirimkan ke semua proses atau tidak sama sekali. Selain itu, umumnya juga diperlukan bahwa semua pesan dikirimkan dalam urutan yang sama ke semua proses. Ini juga dikenal sebagai masalah multicast atomik.

Untuk melihat mengapa atomisitas begitu penting, pertimbangkan database yang direplikasi yang dibangun sebagai aplikasi di atas sistem terdistribusi. Sistem terdistribusi menawarkan fasilitas multicast yang dapat diandalkan. Secara khusus, ini memungkinkan konstruksi kelompok proses yang dapat dikirimkan pesan dengan dapat diandalkan. Basis data yang direplikasi karena itu dibangun sebagai kelompok proses, satu proses untuk setiap replika. Operasi pembaruan selalu di-multicast ke semua replika dan kemudian dilakukan secara lokal. Dengan kata lain, kita mengasumsikan bahwa protokol replikasi aktif digunakan.

Misalkan sekarang bahwa serangkaian pembaruan harus dilakukan, tetapi bahwa selama eksekusi satu dari pembaruan itu, sebuah replika mengalami kegagalan. Akibatnya, pembaruan tersebut hilang untuk replika itu tetapi di sisi lain, itu dilakukan dengan benar di replika lainnya.

Ketika replika yang baru saja mengalami kegagalan pulih, setidaknya bisa pulih ke keadaan yang sama seperti sebelum kegagalan. Namun, mungkin ia telah melewatkan beberapa pembaruan. Pada titik ini, sangat penting bahwa ia dibawa up to date dengan replika-replika lainnya. Membawa replika ke dalam keadaan yang sama dengan yang lain memerlukan bahwa kita tahu dengan pasti operasi-operasi apa yang ia lewatkan, dan dalam urutan apa operasi-operasi ini harus dilakukan.

Sekarang bayangkan bahwa sistem terdistribusi yang mendasarinya mendukung multicast atomik. Dalam hal ini, operasi pembaruan yang dikirimkan ke semua replika tepat sebelum salah satunya mengalami kegagalan entah dilakukan di semua replika yang tidak bermasalah, atau tidak dilakukan sama sekali. Secara khusus, dengan multicast atomik, operasi dapat dilakukan oleh semua replika yang beroperasi dengan benar hanya jika mereka telah mencapai kesepakatan tentang keanggotaan kelompok. Dengan kata lain, pembaruan dilakukan jika replika yang tersisa telah setuju bahwa replika yang mengalami kegagalan tidak lagi termasuk dalam grup.

Ketika replika yang mengalami kegagalan pulih, ia sekarang dipaksa untuk bergabung dalam grup sekali lagi. Tidak ada operasi pembaruan yang akan diteruskan sampai ia terdaftar sebagai anggota lagi. Bergabung dalam grup memerlukan bahwa statusnya diupdate dengan anggota grup yang lain. Oleh karena itu, multicast atomik memastikan bahwa proses yang tidak bermasalah mempertahankan pandangan konsisten tentang database, dan memaksa rekonsiliasi ketika sebuah replika pulih dan bergabung kembali dalam grup.

a. Sinkronisasi Virtual

Multicast yang dapat diandalkan dalam keberadaan kegagalan proses dapat didefinisikan secara akurat dalam hal kelompok proses dan perubahan anggota grup. Seperti yang kita lakukan sebelumnya, kita membuat perbedaan antara menerima dan memberikan pesan. Secara khusus, kita sekali lagi mengadopsi model di mana sistem terdistribusi terdiri dari lapisan komunikasi, seperti yang ditunjukkan di Gambar 8.12. Dalam lapisan komunikasi ini, pesan dikirim dan diterima. Pesan yang diterima disimpan secara lokal di dalam lapisan komunikasi sampai dapat disampaikan ke aplikasi yang secara logis ditempatkan pada lapisan yang lebih tinggi.

Gambar 8.12

Seluruh ide dari multicast atomik adalah bahwa pesan multicast m secara unik terkait dengan daftar proses yang harus menerimanya. Daftar pengiriman ini sesuai dengan pandangan kelompok, yaitu, pandangan tentang set proses yang terkandung dalam kelompok, yang dimiliki pengirim pada saat pesan m di-multicast. Suatu pengamatan penting adalah bahwa setiap proses dalam daftar tersebut memiliki pandangan yang sama. Dengan kata lain, mereka semua harus setuju bahwa m harus disampaikan kepada masing-masing dari mereka dan tidak ada proses lain.

Sekarang, misalkan pesan m di-multicast pada saat pengirimnya memiliki pandangan kelompok G. Selanjutnya, anggaplah bahwa saat multicast berlangsung, proses lain bergabung atau meninggalkan kelompok. Perubahan keanggotaan kelompok ini secara alami diumumkan kepada semua proses di G. Dinyatakan dengan cara yang sedikit berbeda, perubahan pandangan terjadi dengan meng-multicast pesan vc yang mengumumkan bergabung atau meninggalkan suatu proses. Sekarang kita memiliki dua pesan multicast yang bergerak secara bersamaan: m dan vc. Yang perlu kita jamin adalah bahwa m dikirimkan ke semua proses dalam G sebelum masing-masing dari mereka menerima pesan vc, atau m tidak dikirimkan sama sekali. Perlu dicatat bahwa persyaratan ini agak mirip dengan multicast yang diurutkan sepenuhnya, yang dibahas dalam Bab 6.

Sebuah pertanyaan yang cepat muncul adalah bahwa jika m tidak dikirimkan ke proses mana pun, bagaimana kita bisa berbicara tentang protokol multicast yang dapat diandalkan? Pada dasarnya, hanya ada satu kasus di mana pengiriman m diizinkan gagal: ketika perubahan keanggotaan kelompok adalah hasil dari pengirim m mengalami kegagalan. Dalam hal ini, baik semua anggota G seharusnya mendengar tentang pembatalan anggota baru, atau tidak sama sekali. Atau, mungkin m diabaikan oleh setiap anggota, yang sesuai dengan situasi bahwa pengirim mengalami kegagalan sebelum m dikirim.

Bentuk yang lebih kuat dari multicast yang dapat diandalkan ini menjamin bahwa pesan yang di-multicast ke pandangan kelompok G disampaikan kepada setiap proses yang tidak bermasalah di G. Jika pengirim pesan mengalami kegagalan selama multicast, pesan tersebut dapat disampaikan kepada semua proses yang tersisa, atau diabaikan oleh masing-masing dari mereka. Multicast yang dapat diandalkan dengan properti ini dikatakan bersifat virtual synchronous (Birman dan Joseph, 1987).

Bayangkan empat proses yang ditunjukkan pada Gambar 8.13. Pada suatu waktu, proses P1 bergabung dengan kelompok, yang pada saat itu terdiri dari P1, P2, P3, dan P4. Setelah beberapa pesan di-multicast, P3 mengalami kegagalan. Namun, sebelum mengalami kegagalan, ia berhasil melakukan multicast pesan ke proses P2 dan P4, tetapi tidak ke P1. Namun, virtual synchrony menjamin bahwa pesan tersebut sama sekali tidak disampaikan, efektif menetapkan situasi bahwa pesan itu tidak pernah dikirim sebelum P3 mengalami kegagalan.

Gambar 8.13

Setelah P3 dihapus dari kelompok, komunikasi berlanjut antara anggota kelompok yang tersisa. Kemudian, saat P3 pulih, ia dapat bergabung kembali dalam kelompok setelah keadaannya diperbarui.

Prinsip virtual synchrony berasal dari fakta bahwa semua multicast terjadi antara perubahan pandangan. Dinyatakan dengan cara yang sedikit berbeda, perubahan pandangan bertindak sebagai penghalang yang tidak dapat dilalui oleh multicast apa pun. Dalam suatu arti, ini dapat dibandingkan dengan penggunaan variabel sinkronisasi dalam penyimpanan data terdistribusi seperti yang dibahas pada bab sebelumnya. Semua multicasts yang sedang berlangsung saat perubahan pandangan berlangsung diselesaikan sebelum perubahan pandangan tersebut berlaku. Implementasi virtual synchrony tidak sederhana seperti yang akan kita diskusikan secara detail di bawah.

b. Pengurutan Pesan (Message Ordering)

Virtual synchrony memungkinkan pengembang aplikasi untuk mempertimbangkan multicasts sebagai peristiwa yang terjadi dalam epoch yang dipisahkan oleh perubahan keanggotaan grup. Namun, belum ada yang dikatakan tentang pengurutan multicasts. Secara umum, empat pengurutan yang berbeda dibedakan:

• Multicast yang tidak diurutkan
• Multicast yang diurutkan FIFO
• Multicast yang diurutkan sebab-akibat
• Multicast yang diurutkan sepenuhnya

Sebuah multicast yang dapat diandalkan dan tidak diurutkan adalah multicast yang hampir sinkron di mana tidak ada jaminan tentang urutan pengiriman pesan yang diterima oleh proses yang berbeda. Untuk menjelaskan, anggaplah bahwa multicasting yang dapat diandalkan didukung oleh pustaka yang menyediakan primitif kirim dan terima. Operasi terima memblokir proses pemanggil hingga pesan diantar kepadanya.

Sekarang bayangkan pengirim P1 yang melakukan multicasting dua pesan ke suatu grup sementara dua proses lain dalam grup tersebut menunggu pesan tiba, seperti yang ditunjukkan pada Gambar 8-14. Mengasumsikan bahwa proses tidak mengalami kegagalan atau meninggalkan grup selama multicasts ini, mungkin saja lapisan komunikasi di P2 pertama kali menerima pesan m1 dan kemudian m2. Karena tidak ada batasan pengurutan pesan, pesan dapat disampaikan kepada P2 dalam urutan yang diterimanya. Sebaliknya, lapisan komunikasi di P3 mungkin pertama kali menerima pesan m2 diikuti oleh m1, dan menyampaikan keduanya dalam urutan ini kepada P3.

Gambar 8.14. Tiga proses yang berkomunikasi dalam grup yang sama. Urutan peristiwa per proses ditunjukkan di sepanjang sumbu vertikal.

Gambar 8.14

Dalam kasus multicast yang dapat diandalkan dan diurutkan FIFO, lapisan komunikasi dipaksa untuk menyampaikan pesan masuk dari proses yang sama dalam urutan yang sama dengan urutan pengiriman. Pertimbangkan komunikasi dalam suatu grup dari empat proses, seperti yang ditunjukkan dalam Gambar 8-15. Dengan pengurutan FIFO, satu-satunya hal yang penting adalah bahwa pesan m1 selalu disampaikan sebelum m2, dan, demikian pula, bahwa pesan m3 selalu disampaikan sebelum m4. Aturan ini harus ditaati oleh semua proses dalam grup. Dengan kata lain, ketika lapisan komunikasi di P3 menerima m2 terlebih dahulu, itu akan menunggu pengiriman ke P3 sampai m1 diterima dan disampaikan.

Gambar 8.15. Empat proses dalam grup yang sama dengan dua pengirim yang berbeda, dan urutan pengiriman pesan yang mungkin di bawah multicast yang diurutkan FIFO.

Gambar 8.15

Namun, tidak ada batasan tentang pengiriman pesan yang dikirim oleh proses yang berbeda. Dengan kata lain, jika proses P2 menerima m1 sebelum m3, ia dapat menyampaikan kedua pesan tersebut dalam urutan itu. Sementara itu, proses P3 mungkin telah menerima m3 sebelum menerima m1. Pengurutan FIFO menyatakan bahwa P3 dapat menyampaikan m3 sebelum m1, meskipun urutan pengiriman ini berbeda dari P2.

Akhirnya, multicast yang dapat diandalkan dan diurutkan sebab-akibat menyampaikan pesan sehingga kausalitas potensial antara pesan yang berbeda dipertahankan. Dengan kata lain, jika suatu pesan m1 mendahului sebab pesan lain m2, terlepas dari apakah mereka di-multicast oleh pengirim yang sama, lapisan komunikasi di setiap penerima akan selalu menyampaikan m2 setelah menerima dan menyampaikan m1. Perlu dicatat bahwa multicast yang diurutkan sebab-akibat dapat diimplementasikan dengan menggunakan cap waktu vektor seperti yang dibahas dalam Bab 6.

Selain ketiga pengurutan ini, mungkin ada batasan tambahan bahwa pengiriman pesan juga harus sepenuhnya diurutkan. Pengiriman sepenuhnya berarti bahwa terlepas dari apakah pengiriman pesan tidak diurutkan, diurutkan FIFO, atau diurutkan sebab-akibat, diperlukan tambahan bahwa ketika pesan disampaikan, mereka disampaikan dalam urutan yang sama kepada semua anggota grup.

Sebagai contoh, dengan kombinasi multicast FIFO dan sepenuhnya diurutkan, proses P2 dan P3 pada Gambar 8.15 mungkin keduanya pertama kali menyampaikan pesan m3 dan kemudian pesan m1. Namun, jika P2 menyampaikan m1 sebelum m3, sementara P3 menyampaikan m3 sebelum menyampaikan m1, mereka akan melanggar batasan pengurutan sepenuhnya. Perlu dicatat bahwa pengurutan FIFO masih harus dihormati. Dengan kata lain, m2 harus disampaikan setelah m1 dan, sesuai dengan itu, m4 harus disampaikan setelah m3.

Multicast yang dapat diandalkan dan hampir sepenuhnya diurutkan yang menawarkan pengiriman pesan yang sepenuhnya diurutkan disebut multicast atomik. Dengan tiga batasan pengurutan pesan yang berbeda yang dibahas di atas, ini mengarah pada enam bentuk multicasting yang dapat diandalkan seperti yang ditunjukkan dalam Gambar 8.16 (Hadzilacos dan Toueg, 1993).

Gambar 8-16. Enam versi multicasting yang dapat diandalkan dan hampir sinkron.

Gambar 8.16

c. Mengimplementasikan Virtual Synchrony

Mari kita pertimbangkan implementasi yang mungkin dari multicast andal hampir sinkron. Contoh implementasi tersebut muncul dalam Isis, suatu sistem terdistribusi yang tahan kesalahan yang telah digunakan secara praktis di industri selama beberapa tahun. Kita akan fokus pada beberapa isu implementasi teknik ini seperti yang dijelaskan dalam Birman et al. (1991).

Multicast andal dalam Isis menggunakan fasilitas komunikasi titik-ke-titik andal yang tersedia dari jaringan dasar, khususnya, TCP. Multicast sebuah pesan m ke grup proses diimplementasikan dengan mengirimkan m dengan andal kepada setiap anggota grup. Akibatnya, meskipun setiap transmisi dijamin berhasil, tidak ada jaminan bahwa semua anggota grup menerima m. Khususnya, pengirim dapat gagal sebelum berhasil mentransmisikan m ke setiap anggota.

Selain komunikasi titik ke titik yang dapat diandalkan, Isis juga mengasumsikan bahwa pesan dari sumber yang sama diterima oleh lapisan komunikasi sesuai dengan urutan pengirimannya oleh sumber tersebut. Dalam praktiknya, persyaratan ini diselesaikan dengan menggunakan koneksi TCP untuk komunikasi titik-ke-titik.

Masalah utama yang perlu dipecahkan adalah menjamin bahwa semua pesan yang dikirim ke tampilan G diantarkan kepada semua proses yang tidak rusak di G sebelum perubahan keanggotaan grup berikutnya terjadi. Masalah pertama yang perlu diperhatikan adalah memastikan bahwa setiap proses di G telah menerima semua pesan yang dikirimkan ke G. Perlu diperhatikan bahwa karena pengirim pesan m ke G mungkin gagal sebelum menyelesaikan multicasting-nya, mungkin ada proses di G yang tidak akan pernah menerima m. Karena pengirim telah gagal, proses-proses ini seharusnya mendapatkan m dari tempat lain. Bagaimana suatu proses mendeteksi bahwa ia kehilangan pesan dijelaskan selanjutnya.

Solusi untuk masalah ini adalah membiarkan setiap proses di G menyimpan m sampai ia yakin bahwa semua anggota di G telah menerimanya. Jika m telah diterima oleh semua anggota di G, m dikatakan stabil. Hanya pesan yang stabil yang diizinkan untuk diantarkan. Untuk memastikan stabilitas, cukup memilih proses (operasional) sembarang di G dan memintanya untuk mengirimkan m ke semua proses lain.

Lebih spesifik lagi, anggaplah tampilan saat ini adalah Gi, tetapi perlu menginstal tampilan berikutnya Gi+1 . Tanpa kehilangan generalitas, kita dapat menganggap bahwa Gi dan Gi+1 berbeda setidaknya satu proses. Sebuah proses P menyadari perubahan tampilan ketika ia menerima pesan perubahan tampilan. Pesan seperti itu dapat berasal dari proses yang ingin bergabung atau meninggalkan grup, atau dari proses yang telah mendeteksi kegagalan proses di Gi yang sekarang akan dihapus, seperti yang ditunjukkan pada Gambar 8-17(a).

Gambar 8.17. (a) Proses 4 menyadari bahwa proses 7 telah crash dan mengirimkan pesan perubahan tampilan. (b) Proses 6 mengirimkan semua pesan yang tidak stabil, diikuti oleh pesan flush. (c) Proses 6 menginstal tampilan baru ketika telah menerima pesan flush dari semua orang.

Gambar 8.17

Ketika proses P menerima pesan perubahan tampilan untuk Gi+1, ia pertama-tama meneruskan salinan dari setiap pesan tidak stabil dari Gi yang masih dimilikinya ke setiap proses di Gi+1, dan kemudian menandainya sebagai stabil. Ingat bahwa Isis mengasumsikan komunikasi titik-ke-titik andal, sehingga pesan yang diteruskan tidak pernah hilang. Penerusan seperti itu menjamin bahwa semua pesan di Gi yang telah diterima oleh setidaknya satu proses diterima oleh semua proses tidak rusak di Gi. Perlu dicatat bahwa juga akan cukup untuk memilih seorang koordinator tunggal untuk meneruskan pesan yang tidak stabil.

Untuk menunjukkan bahwa P tidak lagi memiliki pesan yang tidak stabil dan bahwa ia siap untuk menginstal Gi+1 segera setelah proses lain dapat melakukannya juga, ia melakukan multicasting pesan flush untuk Gi+1, seperti yang ditunjukkan pada Gambar 8-17(b). Setelah P menerima pesan flush untuk Gi+1 dari setiap proses lain, ia dapat dengan aman menginstal tampilan baru [ditunjukkan pada Gambar 8-17(c)].

Ketika suatu proses Q menerima pesan m yang dikirim dalam Gi, dan Q masih percaya bahwa tampilan saat ini adalah Gi, ia mengantarkan m mempertimbangkan batasan tambahan pengurutan pesan. Jika ia sudah menerima m, ia menganggap pesan itu sebagai duplikat dan membuangnya lebih lanjut.

Karena proses Q pada akhirnya akan menerima pesan perubahan tampilan untuk Gi+1, ia juga akan meneruskan pesan tidak stabil miliknya dan kemudian menyelesaikannya dengan mengirimkan pesan flush untuk Gi+1. Perlu dicatat bahwa karena pengurutan pesan yang mendasari lapisan komunikasi, pesan flush dari suatu proses selalu diterima setelah penerimaan pesan tidak stabil dari proses yang sama.

Kekurangan utama dalam protokol yang telah dijelaskan sejauh ini adalah bahwa ia tidak dapat menangani kegagalan proses saat perubahan tampilan yang baru diumumkan. Khususnya, ia mengasumsikan bahwa sampai tampilan baru Gi+1 telah diinstal oleh setiap anggota di Gi+1, tidak akan ada proses di Gi+1 yang akan gagal (yang akan menyebabkan tampilan berikutnya Gi+2). Masalah ini dipecahkan dengan mengumumkan perubahan tampilan untuk tampilan apa pun Gi+k bahkan ketika perubahan sebelumnya belum diinstal oleh semua proses. Rincian ditinggalkan sebagai latihan untuk pembaca.

https://csis.pace.edu/~marchese/CS865/Lectures/Chap8/Chapter8.htm

Itulah Materi tentang Fault Tolerance dalam Sistem Terdistribusi. Mohon maaf apabila ada kesalahan sedikit pun.

Terima Kasih 😄😘👌👍 :)

Wassalamu‘alaikum wr. wb.