Skip navigation


Tulisan ini diambil dari tugas review artikel berjudul “A Modular Approach To Fault-Tolerant Broadcast and Related Problems“. Artikel ini membahas permasalahan broadcast dan consensus pada sistem yang fault tolerant. Permasalahan-permasalahan tersebut diklasifikasikan berdasarkan spesifikasinya ke dalam beberapa kategori mulai dari kategori terlemah Reliable Broadcast dan kombinasi antara beberapa permasalahan broadcast lainnya.  Kemudian artikel ini akan memberikan algoritma solusi untuk setiap permasalahan. Selanjutnya solusi ini akan dideskripsikan secara moduler mulai dari solusi untuk kategori Reliable Broadcast dan membangun solusi untuk kategori yang lebih kuat dengan menggunakan algoritma-algoritma untuk permasalahan yang lebih lemah.

Broadcast adalah sebuah operasi pada sistem terdistribusi yakni pengiriman pesan dari sebuah proses kepada seluruh proses yang lain yang ada pada sistem. Algoritma broadcast secara umum disusun dengan menggunakan fungsi yang lebih sederhana yakni point to point network. Fungsi ini terdiri dari 2 buah fungsi primitif send dan receive antara 2 buah proses. Di dalam implementasinya terdapat beberapa masalah failure antara lain omission failure dan timing failure. Omission failure adalah ketika pesan gagal terkirim karena adanya crash pada proses ataupun pada link. Sedangkan timing failure adalah kegagalan yang terjadi karena adanya clock dan performance failure yang menyebabkan pesan terkirim dengan waktu yang lebih lama daripada yang diantisipasi pada sistem synchronous.

Seperti yang telah dijelaskan di atas, permasalahan broadcast diklasifikasikan berdasarkan kebutuhan. Klasifikasi ini tersusun mulai dari yang kategori spesifikasi terlemah yakni Reliable Broadcast, FIFO Broadcast, Causal Broadcast, Atomic Broadcast, beberapa spesifikasi kombinasi seperti FIFO Atomic Broadcast serta Causal Atomic Broadcast, kemudian Timed Broadcast, dan terakhir Uniform Broadcast.

Reliable Broadcast membutuhkan semua correct process melakukan deliver untuk himpunan pesan yang sama dan himpunan tersebut berisi pesan yang telah di­-broadcast oleh correct process. Spesifikasi tersebut disusun ke dalam tiga buah properti yakni Validity, Agreement, dan Integrity. Properti Validity mensyaratkan jika sebuah correct process melakukan broadcast sebuah pesan m, maka proses tersebut akan melakukan deliver m. Agreement mensyaratkan jika sebuah correct process melakukan deliver sebuah pesan m, maka semua correct process suatu saat akan melakukan deliver proses m. Sedangkan properti Integrity mensyaratkan untuk setiap pesan m, semua correct process melakukan deliver m maksimal sekali jika m telah di broadcast oleh si pengirim.

Dua buah properti pertama dari Reliable Broadcast memastikan bahwa semua pesan yang dibroadcast oleh sebuah correct process maka akan dideliver juga oleh semua correct process. Jika sebuah proses yang mengirimkan pesan m mengalami faulty maka pesan ini mungkin akan dideliver oleh semua correct process atau tidak sama sekali.

FIFO Broadcast memiliki spesifikasi yang lebih kuat daripada Reliable Broadcast. Pada jenis ini, jika sebuah pesan m dibroadcast sebelum pesan m’ oleh sebuah correct process yang sama, maka tidak ada correct process yang melakukan deliver pesan m’ jika belum melakukan deliver pesan m. Spesifikasi ini mencegah sebuah proses menerima sebuah pesan yang memiliki hubungan dengan pesan sebelumnya. Salah satu contoh aplikasi yang membutuhkan spesifikasi ini adalah reservasi tiket pesawat. Aksi melakukan pembatalan reservasi seharusnya diterima setelah adanya aksi melakukan pemesanan tiket.

Jika pada FIFO Broadcast urutan deliver sebuah pesan dilakukan berdasarkan urutan broadcast dari sebuah correct process, maka pada Causal Broadcast urutan deliver sebuah pesan dilakukan berdasarkan kausalitas pesan tersebut. Sebuah deliver pesan oleh sebuah proses dapat menyebabkan proses tersebut akan melakukan broadcast pesan yang lain. Untuk beberapa skenario spesifikasi seperti ini dibutuhkan. Misalnya terdapat sebuah proses A yang melakukan broadcast sebuah pesan, kemudian proses B melakukan broadcast pesan berupa respons untuk pesan yang dibroadcast oleh A, maka jika pada C proses delivery pesan kedua dilakukan terlebih dahulu dari pesan pertama maka C dapat mengalami misinterpretasi. Causal Broadcast dispesifikasikan sebagai berikut: jika broadcast sebuah pesan m mengakibatkan broadcast pesan m’ maka tidak ada correct process yang melakukan deliver m’ jika sebelumnya tidak melakukan deliver m.

Casual Broadcast tidak mensyaratkan urutan deliver dua buah pesan jika keduanya tidak terhubung secara kausal. FIFO Broadcast juga tidak mensyaratkan urutan keduanya jika tidak berasal dari sebuah proses yang sama. Hal ini dapat menyebabkan ketidakkonsistenan pada beberapa skenario. Contohnya adalah skenario transaksi pada bank yang menggunakan data redundan. Misalnya terdapat sebuah rekening dengan saldo $100. Pada saat yang bersamaan terdapat perintah untuk melakukan penarikan $20 dan penambahan bunga sebanyak 10%. Karena keduanya tidak mengakibatkan satu sama lain dan tidak dibroadcast oleh proses yang sama maka spesifikasi Casual Broadcast dan FIFO Broadcast tidak berlaku. Akan tetapi jika antara dua buah tempat, keduanya dideliver dengan urutan yang berbeda maka akan menimbulkan inkonsistensi.

Hal di atas dapat dicegah dengan spesifikasi Atomic Broadcast. Pada spesifikasi ini sebuah pesan akan dideliver dengan urutan yang sama oleh semua proses. Dengan demikian view dari proses-proses tersebut akan sama oleh sistem. Atomic Broadcast sebenarnya merupakan Reliable Broadcast dengan tambahan sebuah properti yakni Total Order. Total Order ini didefinisikan sebagai berikut: jika dua buah proses p dan q melakukan deliver pesan m dan m’, maka p kan melakukan deliver m sebelum m’ jika dan hanya jika q melakukan deliver pesan m sebelum m’.

Atomic Broadcast sendiri juga tidak mensyaratkan hal seperti yang disyaratkan oleh FIFO Broadcast. Misalnya sebuah proses mengalami transient failure ketika broadcast m kemudian melakukan broadcast m’, dengan demikian semua correct process akan melakukan deliver m’. FIFO Atomic Broadcast merupakan kombinasi antara keduanya.

Meski sudah lebih kuat, FIFO Atomic Broadcast juga tidak mensyaratkan deliver pesan harus dilakukan dengan urutan kausalitas. Contohnya sama seperti pada contoh Causal Broadcast sebelumnya. Sebuah faulty process A mengirimkan broadcast pesan. Kemudian sebuah faulty process B, yang merupakan satu-satunya yang melakukan delivery, melakukan broadcast pesan respons sebelum akhirnya crash. Correct process C melakukan delivery pesan dari B sementara tidak mendapat pesan dari A. Oleh karena itu juga ada spesifikasi Causal Atomic Broadcast yang lebih kuat dari FIFO Atomic dan Causal Broadcast.

Timed Broadcast adalah sebuah spesifikasi yang dibutuhkan oleh aplikasi yang mensyaratkan jika delivery dilakukan maka delivery tersebut dilakukan pada sebuah rentang waktu setelah pesan dibroadcast. Properti ini disebut ∆-Timeliness.  Pengukuran ini dapat dilakukan dengan menggunakan real time yang dilakukan oleh sebuah proses pengamat ataupun local time oleh prose situ sendiri. Kedua cara tersebut disebut Real-Time ∆-Timeliness dan Local-Time ∆-Timeliness. Pada Real-Time ∆-Timeliness terdapat sebuah konstanta sedemikian sehingga jika sebuah pesan m dibroadcast pada saat real time t, maka tidak ada proses yang benar yang melakukan deliver m setelah real time t+∆. Sedangkan pada Local-Time ∆-Timeliness terdapat sebuah konstanta sedemikian sehingga tidak ada proses p men-deliver pesan m setelah local time ts(m) + ∆ pada clock milik p.

Properti Agreement, Integrity, Order, dan ∆-Timeliness disepsifikasikan dengan tidak adanya pesan yang dideliver oleh faulty process. Spesifikasi ini kadang tidak diinginkan dalam beberapa aplikasi. Sebagai contoh pada properti Agreement faulty process dapat melakukan deliver sebuah pesan yang tidak dideliver oleh correct process. Oleh karena itu dibutuhkan spesifikasi yang memperkuat properti-properti tersebut. Sebuah properti yang Uniform berlaku untuk baik correct process maupun faulty process.



Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: