Review Artikel “A Modular Approach to Fault-Tolerant Broadcasts and Related Problem” : Broadcast


Beres juga akhirnya tugas Sistem Terdistribusi Lanjut, me-review bab3 dari artikel “A Modular Approach to Fault-Tolerant Broadcasts and Related Problem” . Kali ini aku ga telat lagi ngumpulin tugasnya, hehe… Kali ini, review-nya seputar konsep Broadcast, yg merupakan salah satu konsep penting bagi Sistem Terdistribusi Lanjut. *Kenyataannya apa yg aku tulis di sini ga semuanya review.. ada yg cuma sekadar terjemahan b. inggris karena ga terlalu ngerti -_-*. Selamat menikmati :D

BROADCAST

Broadcast merupakan salah satu fungsi penting yang dimiliki oleh sistem terdistribusi yang mana bertugas untuk menyebarkan pesan secara langsung ke semua proses/entitas pada sistem. Broadcast memiliki banyak jenis,terbagi berdasarkan mekanisme atau cara melakukan broadcast terhadap sebuah pesan. Pengimplementasian tipe broadcast pada sistem terdistribusi akan sangat bergantung pada permasalahan yang ingin dipecahkan oleh sistem tersebut. Tipe broadcast A mungkin dapat cocok dengan suatu sistem, dimana tipe broadcast B tidak cocok dengan sistem tersebut.

Berikut ini berbagai jenis broadcast yang ada untuk keperluan berbagai sistem terdistribusi:

Reliable Broadcast

Secara informal, Reliable Broadcast mensyaratkan bahwa semua proses yang benar men-deliver himpunan pesan yang sama (Agreement), dan himpunan tersebut mencakup semua pesan yang di-broadcast oleh proses yang benar (Validity) dan tidak ada pesan yang salah atau palsu (Integrity). Secara formal, Reliable Broadcast didefinisikan dengan 2 primitif yaitu broadcast dan deliver. Ketika sebuah proses p melakukan broadcast dengan sebuah pesan m sebagai parameter, dapat ditulis p broadcasts m. Kita asumsikan bahwa m diambil dari sebuah himpunan M yang merupakan himpunan pesan-pesan yang mungkin. Ketika sebuah proses q mengembalikan eksekusi dari aksi deliver terhadap pesan m sebagai nilai kembalian, dapat ditulis q delivers m.

Reliable Broadcast merupakan sebuah broadcast yang memenuhi 3 buah properti yaitu :

  1. Validity: Jika sebuah proses yang benar p mem-broadcast sebuah pesan m, maka pada akhirnya p men-deliver m.
  2. Agreement: Jika sebuah proses yang benar p men-deliver sebuah pesan m, maka semua proses yang benar pada akhirnya akan men-deliver m.
  3. Integrity: Untuk setiap pesan m, setiap proses yang benar men-deliver m paling banyak 1 kali, dan hanya jika m telah di-broadcast sebelumnya oleh sender(m).

FIFO Broadcast

Secara umum, setiap pesan memiliki sebuah konteks yang tidak boleh disalahartikan. Pesan seperti ini seharusnya tidak boleh di-deliver oleh sebuah proses yang tidak mengetahui konteks tersebut. Pada beberapa aplikasi, konteks dari sebuah pesan m terdiri dari pesan-pesan yang sebelumnya di-broadcast oleh sender m. Sebagai contoh, pada sistem reservasi airline, pesan pembatalan reservasi memiliki konteks yang terdiri dari pesan-pesan yang membuat reservasi. Jika terjadi pembatalan, maka pesan pembatalan seharusnya tidak di-deliver ke tempat yang  belum pernah menerima pesan reservasi. Aplikasi seperti ini membutuhkan FIFO Broadcast. FIFO Broadcast merupakan sebuah Reliable Broadcast yang memiliki tambahan properti FIFO Order yaitu jika sebuah proses mem-broadcast sebuah pesan m sebelum pesan tersebut mem-broadcast pesan m’, maka tidak ada proses yang benar akan men-deliver m’ jika proses tersebut belum men-deliver m.

Causal Broadcast

FIFO Order dirasa cukup ketika konteks dari sebuah pesan m terdiri atas hanya pesan-pesan yang sebelumnya di-broadcast oleh sender m sebelum m. Sebuah pesan m mungkin juga bergantung pada pesan-pesan yang di-deliver oleh sender m sebelum m.  Untuk kasus ini, urutan message delivery yang dijamin oleh FIFO Broadcast tidaklah cukup. Sebagai contoh, pada sebuah aplikasi network news, jika pengguna mendistribusikan artikel-artikel dengan FIFO Broadcast, ada skenario yang tidak diinginkan bakal terjadi. Sebagai ilustrasi, User A mem-broadcast sebuah artikel. User B, di tempat yang lain, men-deliver artikel tersebut dan mem-broadcast sebuah respon yang hanya dapat dimengerti oleh user yang sudah melihat artikel aslinya. User C men-deliver respon B sebelum melakukan deliver terhadap artikel asli dari A dan akibatnya terjadi kesalahan interpretasi respon. Causal Broadcast merupakan penguatan dari FIFO Broadcast yang mencegah problem seperti yang telah diceritakan dengan menambahkan aturan baru yaitu sebuah pesan depend on pesan lainnya, dan menjamin bahwa sebuah pesan tidak akan di-deliver hingga semua pesan yang depend on pesan tersebut telah di-deliver.

Secara formal, Causal Broadcast dapat didefinisikan sebagai sebuah Reliable Broadcast  yang memiliki properti tambahan Causal Order yaitu jika aksi broadcast terhadap pesan m secara kausal mendahului broadcast  terhadap pesan m’, maka tidak ada proses yang benar melakukan deliver m’ apabila proses tersebut sebelumnya tidak men-deliver m.

Atomic Broadcast

Causal Broadcast tidak mampu menangani kasus jika terdapat dua buah broadcast yang pesan-pesannya tidak berhubungan secara kausal. Sebagai contoh, terdapat sebuah basis data yang tereplikasi dengan 2 buah copy sebuah akun bank x, berada site yang berbeda. Pertama-tama, x memiliki sebuah nilai sebesar $100. Seorang user menabung sebesar $20, memicu sebuah aksi broadcast berupa “tambahkan $20 ke x” ke dua buah copy x. Pada saat yang bersamaan, di site yang berbeda, bank menginisiasi sebuah broadcast berupa “tambahkan 10% bunga ke x”. Karena kedua buah broadcast ini tidak berhubungan kausal, Causal Broadcast memperbolehkan 2 copy dari x untuk men-deliver pesan-pesan tersebut dengan urutan berbeda. Dengan demikian, akan terjadi inkonsistensi pada database.

Atomic Broadcast mensyaratkan bahwa semua proses yang benar men-deliver semua pesan dengan urutan yang sama. Hal ini akan menyebabkan semua proses memiliki “view”Secara formal, Atomic Broadcast adalah sebuah Reliable Broadcast yang memenuhi properti  Total Order yaitu jika 2 proses yang benar p dan q masing-masing men-deliver pesan m dan m’, maka p deliver m sebelum m’ jika dan hanya jika q deliver m sebelum m’. Dengan demikian, persyaratan Agreement dan Total Order berimplikasi bahwa proses-proses yang benar pada akhirnya akan men-deliver urutan pesan yang sama.

FIFO Atomic Broadcast

Atomic Broadcast tidak mensyaratkan bahwa pesan-pesan  harus di-deliver dengan urutan FIFO. Sebaga contoh, Atomic Broadcast memperbolehkan skenario sebagai berikut: sebuah proses sedang mengalami failure selama aksi broadcast dari sebuah pesan m dilakukan, dan kemudian mem-broadcast m’, dan proses-proses yang benar hanya akan  men-deliver m’. Dengan demikian, Atomic Broadcast dapat dikatakan tidak lebih kuat dibandingkan FIFO Broadcast.

Oleh karena itu, didefinisikan FIFO Atomic Broadcast yang mampu menangani permasalahan tersebut. FIFO Atomic Broadcast merupakan sebuah Reliable Broadcast yang memenuhi persyaratan FIFO Order dan Total Order.

Causal Atomic Broadcast

FIFO Atomic Broadcast tidak mensyaratkan bahwa pesan-pesan di-deliver dalam urutan Causal. Ingat kembali kasus pada network news, dan anggap jaringan tersebut menggunakan FIFO Atomic Broadcast untuk menyebarkan artikel. Dengan penggunaan FIFO Atomic Broadcast, dapat terjadi skenario seperti ini: User A yang failure mem-broadcast sebuah artikel. Lalu, User B yang failure (yang merupakan satu-satunya yang men-deliver pesan tersebut) mem-broadcast sebuah respon dan seketika setelahnya terjadi crash (sebelum men-deliver respon tersebut). Maka, FIFO Atomic Broadast tidak menjamin Causal Order.

Dengan demikian, didefinisikan Causal Atomic Broadast yan g merupakan sebuah Reliable Broadast yang memenuhi persyaratan Causal Order dan Total Order. Causal Atomic Broadcast lebi h kuat dibandingkan FIFO Atomic Broadcast maupun Causal Broadcast. Jenis broadcast ini merupakan mekanisme kunci dari pendekatan State Machine untuk membangun fault-tolerance.

Timed Broadcast

Banyak aplikasi yang mensyaratkan bahwa apabila sebuah pesan di-deliver, pesan tersebut akan di-deliver dalam kurun waktu terbatas setelah di-broadcast. Properti tersebut biasa disebut dengan ∆-Timeliness. Seperti biasa, pada sebuah sistem terdistribusi elapsed time dapat diinterpretasikan dengan 2 cara yang berbeda: 1) real time (diukur oleh external observer), dan 2)local time (diukur oleh local clock dari proses). Kedua hal ini memunculkan 2 cara yang berbeda pula dalam mendefinisikan  properti ∆-Timeliness, yaitu sebagai berikut.

  1. Real-Time ∆-Timeliness

Terdapat sebuah konstanta sedemikian sehingga jika sebuah pesan m di-broadcast pada saat real time t, maka tidak ada proses yang benar yang men-deliver m setelah real time t+

  1. 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.

Setiap broadcast yang memenuhi properti ∆-Timeliness dapat disebut sebagai timed broadcast. Sebagai contohnya, Timed Reliable Broadcast merupakan sebuah Reliable Broadast yang memenuhi Local- atao Real-Time ∆-Timeliness.

Uniform Broadcast

Properti Agreement, Integrity, Order, dan ∆-Timeliness dari broadcast telah didefinisikan semua untuk membentuk berbagai jenis broadcast yang sesuai dengan kebutuhan pemecahan suatu masalah. Sejau h ini, tidak ada batasan pada aksi message delivery oleh proses yang fault. Selama masih berhadapan dengan failure yang jinak, kondisi seperti ini masih dapat dicapai.

Sebagai contoh, properti Agreement menyatakan bahwa jika sebuah proses yang benar me-deliver sebuah pesan m, maka semua pross yang benar pada akhirnya me-deliver m. Syarat ini masih memperbolehkan sebuah proses fault men-deliver sebuah pesan yang tidak pernah di-deliver oleh proses yang benar. Kelakuan seperti ini pada banyak aplikasi tidak diinginkan, seperti Atomic Commitment pada basis data terdistribusi, dan dapat dihindari jika failure-nya jinak. Untuk failure tersebut, dapat ditangani dengan memperkuat properti Agreement menjadi Uniform Agreement, yaitu jika sebuah proses (benar atau fault)  me-deliver sebuah pesan m, maka semua proses yang benar pada akhirnya akan me-deliver m. Hal yang sama dapat dilakukan terhadap properti-properti lainnya seperti Integrity, FIFO Order, Local Order, Causal Order, Total Order, dsb, menjadi Uniform Integrity, Uniform FIFO Order, Uniform Local Order,Uniform Causal Order, Uniform Total Order, dsb.

Pada intinya, tambahan sifat uniform akan menyebabkan broadcast memungkinkan semua proses mampu melakukan broadcast atau deliver, terlepas dari apakah proses tersebut benar atau fault.

Review Artikel “A Modular Approach to Fault-Tolerant Broadcasts and Related Problem” : Broadcast

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s