Komunikasi diperlukan untuk beragam tugas di system tersebar. Primitif komunikasi sangat mempengaruhi kemudahan dan efisiensi aplikasi.
1. Pengalamatan dan Penamaan
Nama adalah identifier yang dapat diinterpretasi pemakai atau program. Identifier atau alamat adalah yang dapat diinterpretasi mesin. Nama diterjemahkan menjadi bentuk untuk menjalankan aksi sumber daya yang diacu.
Penamaan dan pengalamatan sumber daya/objek di sistem tersebar harus global tidak bergantung lokasi objek, dapat diskala untuk sistem besar dan diterjemahkan secara efisien sehingga tidak mengurangi kinerja system.
Pengalamatan
Di Internet (TCP/IP), identifier berisi dua bagian, yaitu:
- Host identifier, disebut alamat IP berisi empat oktet (byte)
- Port number (integer 2 byte) mengidentifikasi port komunikasi tertentu.
Cara Implementasi Pengalamatan:
- Dipasang pada kode client secara langsung
- Terdapat nama server, name server mencarikan alamat untuk suatu nama tertentu.
2. Primitif Komunikasi
Jaringan komunikasi menyediakan sarana pengiriman aliran bit data. Primitif komunikasi adalah bentukan level tinggi, dipakai program untuk berkomunikasi menggunakan jaringan komunikasi. Primitif komunikasi sangat mempengaruhi kemudahan penggunaan dan efisiensi aplikasi.
Primitif komunikasi dapat dikategorikan menjadi berikut:
- Primitif komunikasi dua pihak
- Primitif komunikasi kelompok
Komunikasi Dua Pihak
Terdapat dua model primitif komunikasi dua pihat yang popular, yaitu:
- Model massage-passing
- Remote Procedure call (RPC)
Model Massage-Passing
Layanan komunikasi direduksi menjadi dua system call, yaitu:
- Send (destination, message)
- Receive (sourceAddress, message)
Send (Destination, Message)
Mengirim pesan (message) ke proses tujuan (destination).
Receive (SourceAddress, Message)
Menyebabkan pemanggil menunggu pesan (message) dari alamat sumber (sourceAddress). Ketika pesan tiba, pesan dikopi ke buffer proses.
Masalah
- Hilangnya pesan dijaringan.
- Authentication, menjamin komunikasi benar-benar diotorasi.
- Kinerja bila message passing diterapkan pada proses-proses di mesin sama.
Ringkasan alternatif rancangan dan implementasi massage-passing
3. Tabel Masalah-masalah Perancangan Sistem Message Passing
Masalah-masalah pada perancangan dan implementasi system message passing:
1. Masalah pengalamatan (addressing), alternatif
Pengalamatam langsung (direct)
Proses pengirim
Proses penerima, mempunyai alternative
- Pengalamatan eksplisit
- Pengalamatan implicit
Pengalamatan tak langsung (indirect)
- Pengalamatan statis
- Pengalamatan dinamis
- Pengalamatan kepemilikan
2. Masalah sinkronisasi proses (synchronization)
Pada proses pengirim (send)
- Blocking, yaitu setelah mengirim (send) maka proses di-blocked menunggu jawaban proses yang dikirimi.
- Non-bloking, yaitu setelah mengirim (send) maka proses terus melanjutkan eksekusi instruksi-instruksi berikutnya.
Pada proses penerima (receive)
- Blocking, yaitu setelah menyatakan menerima (receive) maka proses di-blocked menunggu kiriman pesan dari proses yang diinginkan.
- Non-blocking, yaitu setelah menyatakan menerima (receive) maka proses terus melanjutkan eksekusi instruksi-instruksi berikutnya.
- Masalah pada penerima adalah cara implementasi pemeriksaan kedatangan pesan.
3. Masalah buffering
- Bufferred primitives
- Unbuffered primitives
4. Masalah kehandalan
- Reliable primitives
- Unreliable primitives
5. Masalahh format pesan (message format)
Isi pesan (content)
- Pesan dengan panjang tetap
- Pesan dengan panjang dapat beragam
6. Masalah disiplin antrian (queueing discipline)
Message passing mempunyai banyak keunggulan, diantaranya kemampuan transparan system computer baik uniprocessor dengan memori bersama ataupun system tersebar.
Remote Procedure Calls
Tujuan RPC adalah pemanggilan prosedur jauh (dikerjakan di mesin lain) seperti pemanggilan prosedur lokal. Pemrogram menulis program seperti biasa tampa peduli apakah prosedur akan dijalankan di pemroses setempat atau di pemroses jauh.
RPC memungkinkan proses di satu system memanggil prosedur dip roses lain di mesin lain. Prosedur pemanggil dan yang dipanggil dapat berada di mesin terpisah dengan ruang alamat memori terpisah. Karena tidak ada memori global bersama seperti di satu proses maka dilakukan transfer informasi melalui para meter pada panggilan RPC.
RPC biasanya diimplementasikan pada system message passing. Panggilan ke prosedur-prosedur di mesin lain diterjemahkan menjadi pengirim pesan, yaitu:
- Send (RemoteProses, InputParameters)
- Receive (RemoteProses, OutputParameters)
Mekanisme RPC
Gambar 1 Skema Mekanisme RPC
Pada gambar, panggilan remote terdiri 10 langkah:
Langkah 1
Program (prosedur) client memanggil stub yang di-link di ruang alamat program. Parameter-parameter dilewatkan seperti malakukan panggilan local. Stub client mengepak parameter-parameter menjadi pesan, disebut parameter marshalling.
Langkah 2
Pesan dilewatkan ke lapisan transport untuk transmisi. Pada banyak system, langkah 2 merupakan jebakan (trap) ke system operasi.
Langkah 3
Pada LAN tak koneksi, entitas transport hanya mencantolkan header ke pesan dan meletakan ke jaringan. Pada WAN, lapisan transport lebih rumit.
Langkah 4
Ketika pesan tiba di server, entitas transport melewatkan ke stub server yang membongkar (unmarshaling) pesan menjadi parameter-parameter.
Langkah 5
Stub server memanggil prosedur server, melewatkan parameter-parameter secara standar. Prosedur server tidak mengetahui sedang diaktifkan secara remote karena pemanggil mematuhi semua aturan standar prosedur lokal. Hanya stub yang mengetahui.
Langkah 6
Setelah menyelesaikan kerja, prosedur server selesai seperti prosedur lain selesai. Server dapat mengirim hasil ke pemanggil.
Langkah 7
Stub server me-marshall hasil sebagai pesan dan melepas ke lapisan transport dengan panggilan system (system call) seperti langkah 2.
Langkah 8
Jawaban tiba di mesin client
Langkah 9
Jawaban ditangani stub client
Langkah 10
Stub client kembali kepemanggil, prosedur client. Suatu nilai yang dikirim server dilangkah 6 diberikan ke client.
Tujuan mekanisme RPC adalah memberi ilusi ke prosedur client tidak sedang melakukan panggilan ke server jauh. Client tidak mengetahui bahwa yang melayaninya adalah server jauh. RPC menyembunyikan semua komunikasi jaringan di prosedur stub. Cara ini melindungi program aplikasi, client dan server harus memperhatikan rincian socket dan jaringan lainnya, mempermudah penulisan aplikasi tersebar.
Sumber masalah
- Karena prosedur pemanggil dan yang dipanggil di mesin-mesin berbeda, prosedur-prosedur dieksekusi di ruang alamat berbeda.
- Parameter dan hasil harus dilewatkan (melalui jaringan), lebih rumit jika mesin-mesin tidak identik.
- Mesin dimana prosedur pemanggil dan yang dipanggil dijalankan dapat crash dan kegagalan dapat menimbulkan masalah-masalah rumit.
Pokok-pokok Bahasan RPC
- pelewatan parameter (parameter passing)
- pengikatan (binding)
- pemilihan protokol transport
- penanganan kesalahan (exception hanling)
- semantiks pemanggilan
- representasi data
- penanganan orphan
- kinerja
- keamanan
- masalah spesifik implementasi
Pelewatan Parameter (Parameter Passing)
- Call-by-value dapat diterapkan secara mudah, dengan mengirim kopian data lewat pesan.
- Call-by-reference agak menyusahkan. Banyak usulan penyelesai masalah call-by-reference.
Peningkatan (Binding)
Peningkatan sasaran komunikasi (server yang mengeksekusi prosedur). Terdapat dua komponen pengikatan:
- Menemukan host jauh sebagai server yang dituju
- Menemukan proses server yang cocok di host
Salah satu cara adalah menyediakan basisdata terpusat. Client menghubungi otoritas pusat untuk menemukan layanan tertentu. Cara lain adalah client mengetahui host yang harus di hubungi.
Pemilihan Protokol Transport
Protokol transport dapat beragam antara lain:
- SUN RPC menggunakan UDP dan TCP, conection-oriented atau connectionless.
- Xerox Courier RPC menggunakan SPP, connection-oriented
- Apollo RPC menggunakan UDP, DDS, connectionless.
Bila digunakan connectionlees, client stub harus menangani paket yang hilang dan sebagainya. Protokol connection-oriented menangani kasus paket hilang, terduplikasi dan sebagainya, dengan overhead lebih tinggi dibanding connectionlees.
Penanganan Kesalahan (Exception Handling)
Sumber kesalahan yang sering terjadi adalah:
- Client tidak dapat menemukan lokasi server.
- Pesan request (permintaan) dari client ke server hilang.
- Pesan reply (jawaban) dari server ke client hilang.
- Server crash setelah menerima request.
- Client crash setelah mengirim pesan request.
Semantiks Pemanggilan
Alternatif mengartikan kegagalan (semantiks kegagalan):
- At least once, menjamin server crash telah mengeksekusi sekali atau lebih.
- At most once, tak ada panggilan yang dieksekusi lebih dari satu kali.
- Maybe, system tidak menjamin apapun, paling mudah diimplementasikan.
Representsi Data
Mesin-mesin berbeda menggunakan konversi representasi internal berbeda.
Penanganan Orphan
Client crash setelah memulai RPC dapat menimbulkan masalah. Begitu prosedur server dimulai, proses terus berjalan meskipun client pemanggil crash. Server yang berjalan tanpa client yang menunggu disebut orphan.
Kesulitan disebabkan orphan:
- Menyiakan siklus CPU dan sumber daya lain.
- Orphan mungkin mengunci file dan objek lain sehingga server menolak pengaksesan proses-proses lain.
- Jika client boot ulang dan memulai RPC berulang-ulang, hasil yang dikirim orphan dapat menyebabkan kekacauan.
Penanganan masalah orphan:
- Extermination
- Expiration
- Reincarnation
- Gentle reincarnation.
Extermination
Ketika mesin client pulih setelah crash, memeriksa kelanjungan RPC. Jika masih berlanjut, meminta membunuh proses-proses sedang berjalan sesuai kepentingan. Stub client perlu log RPC sebelum eksekusi. Ketika RPC selesai, isian-isian log RPC tertuda dihapus. Log harus disimpan sehingga lolos dari crash (misalnya di disk).
Orphan dapat menciptakan grand orphan (bahkan great grand orphan). Algoritma extermination harus berjalan rekursif membunuh semua rantai kebawah.
Expiration
Tidak perlu log. Ketika RPC dimulai, server diberi sejumlah waktu penyelesaian panggilan. Jika panggilan tidak selesai dalam interval tertentu, stub server meminta stub client satu kuantum baru. Jika mesin client telah crash atau boot lagi, kejadian ini akan dideteksi, timer tidak akan diperbaharui, dan server di ijinkan mari.
Reincarnation
Dapat terjadi kegagalan extermination untuk eliminasi orphan. Misalnya jika jaringan dipartisi saat dijalankan extermination, beberapa prphan tidak terjangkau. Salah besar bila membunuh semua aktivitas remote di jaringan.
Pada metode reincarnation, waktu dibagi menjadi epoch-epoch sekuel. Ketika client gagal extermination orphan-orphannya, client broadcast awal epoch baru ke semua mesin. Mesin-mesin bereaksi membunuh semua proses server.
Getle Reincarnation
Serupa pendekatan ketiga,tapi kurang mematikan.
Metode ini juga menggunakan epoch-epoch tapi tiap mesin tidak membunuh semua aktivitas remote ketika epoch baru dideklarasikan, mencoba menemukan client yang memulai server. Jika client itu tidak dapat ditemukan, server membunuh proses server untuk client itu.
Kinerja
Umumnya penurunan kinerja RPC disbanding local Procedure call sebesar factor 10 atas lebih.
Keamanan
RPC menimbulkan peluang masalah keamanan seperti pada eksekusi perintah secara remote. Memungkinkan program memangil prosedur di server jauh serupa dengan mengeksekusi perintah di system itu.
Masalah Spesifik Implementasi
- Penerapan ACK
- Penanggulangan jalur kritis
- Pengkopian
- Manajemen timer
3. Komunikasi Kelompok
System message passing dan RCP adalah komunikasi dua pihak, client dan server. Pada system tersebar, komunikasi dapat melibatkan banyak proses sekaligus, tidak hanya dua. Misalnya sekelompok file server memberi layanan file dan untuk menyediakan kemampuan fault tolerance. Pada system fault-tolerant, client mengirim pesan ke semua server untuk menjamin dilayani setidaknya oleh satu server. System tersebar memerlukan mekanisme konumikasi kelompok.
RCP tidak dapat menangani komunikasi satu pengirim ke banyak penerima kecuali dengan banyak RCP terpisah untuk masing-masing server.
Kelompok adalah kumpulan proses yang bertindak bersama. Property utama komunikasi kelompok adalah saat pesan dikirim kekelompok, semua anggota kelompok menerimanya. Komunikasi one-to-many satu pengirim,banyak penerima) berbeda dengan komunikasi point-to-point(satu pengirim,satu penerima)
Tujuan utama kelompok adalah memungkinkan proses berurusan dengan kumpulan proses sebagai satu abstraksi tunggal. Proses dapat mengirim pesan ke kelompok server tanpa mengetahui jumlah server atau lokasinya, yang dapat berubah setiap saat.
Pengelolaan Kelompok
Kelompok bersifat dinamis, yaitu:
- Kelompok baru dapat diciptakan
- Kelompok lama dapat dihapus
- Proses dapat bergabung ke suatu kelompok atau meninggalkan kelompok.
- Prosea dapat menjadi anggota beberapa kelompok sekaligus pada satu waktu.
Untuk itu diperlukan manajemen kelompok dan keanggotaan kelompok.
Masalah pengelolaan kelompok antara lain:
- Operasi-operasi dasar pengelolaan kelompok.
- Pemilihan kelompok tertutup atau terbuka
- Pemilihan kelompok setingkat atau hirarki
- Penaganan keanggotaan kelompok
- Penaganan masalah pengalamatan kelompok.
- Penaganan masalah kelompok-kelompok yang bertumpang tindih.
- Penaganan masalah skalabilitas.
Operasi-operasi Dasar Pengelolaan Kelompok:
- Operasi penciptaan group baru
- Operasi penghapusan group
- Operasi join ke suatu group
- Operasi meninggalkan suatu group
Pemilihan kelompok tertutup atau terbuka
Kelompok tertutup (close group) berarti hanya anggota-anggota di kelompok yang dapat mengirim pesan ke kelompok itu. Proses di luar kelompok tidak dapat mengirim pesan secara langsung ke kelompok secara keseluruhan, meskipun dimungkinkan mengirim ke anggota kelompok secara individu.
Biasanya digunakan untuk pemrosesan pararel yang mempunyai suatu tujuan dan tidak berinteraksi dengan proses-proses luar.
Kelompok terbuka (open group) berarti maka sembarang proses dapat mengirim ke suatu kelompok.
Digunakan bila proses diluar kelompok mengirim ke kelompok.
Pemilihan Kelompok Setingkat atau Hirarki
Kelompok setingkat berarti proses-proses di kelompok itu dianggap setingkat. Pada hirarki terapat peringkat proses, seperti satu proses sebagai coordinator dan yang lainya adalah pekerja. Coordinator memutuskan pekerja yang menangani permintaan.
Kelompok setingkat adalah simetrik, tidak terdapat satu titik tunggal kegagalan. Pembuatan keputusan adalah lebih rumit, terdapat overhead pemrosesan yang lebih banyak.
Pada kelompok berhirarki, kegagalan coordinator menyebabkan seluruh kelompok menjadi mati.
Penaganan keanggotaan kelompok
Penaganan paling sederhana adalah dengan membuat satu server kelompok untuk pengelolaan kelompok. Cara ini mempunyai kelemahan terpusat, yaitu satu titik tunggal kegagalan.
Kebalikannya yaitu secara tersebar. Pada, client mengirim pesan ke semua anggota kelompok yang memberitahukan keberadaannya.
Dua masalah:
- anggota kelompok mengalamai crash
- jika banyak mesin mati dan kelompok tidak lagi mampu beroperasi sama sekali.
Anggota Kelompok mengalami crash
Penyelesaian berbeda untuk tipe system berdasarkan:
Asinkron
Proses lainyang mengetahui proses crash memberitahu ke system. Begitu di pastikan chash, prose situ dihilangkan dari daftar anggota kelompok.
Sinkron
Meninggalkan dan masuk ke kelompok dilakukan secara sinkron.
Jika Banyak Mesin Mati dan Kelompok Tidak Lagi Mampu Beroperasi Sama Sekali.
Diperlukan suatu protocol untuk pembangunan kembali kelompok.
Penaganan Masalah Pengalamatan Kelompok
Bila jaringan mendukung multicasting, maka alamat kelompok diasosiasikan dengan alamat multicast sehingga setiap pesan yang dikirim kealamat kelompok dapat di-multicast. Pesan hanya dikirim ke mesin-mesin yang memerlukan.
- Jika jaringan hanya mendukung broadcast, maka pesan dapat di-broadcast
- Jika jaringan hanya mendukung broadcast, maka kernel mengirim ke mesin-mesin di daftar mesin yang termasuk dalam kelompok yang dituju. Kernel mengirim satu per satu.
Penaganan Masalah Kelompok-kelompok yang Bertumpang Tindih.
System yang memungkinkan keanggotaan kelompok yang tumpang tindih dapat mengakibatkan inkonsistesi bila suatu pesan ayng ditujukan kebeberapa kelompok sekalugus diterima proses yang masuk dalam beberapa kelompok itu.
Penaganan Masalah Skalabilitas.
Harus dipergunakan algortma yang bagus untuk suatu kelompok kecil sekaligus besar sehingga ketika system berkembang tidak diperluakan secara total.
Jenis-jenis Broadcast
Komunikasi kelompok paling mudah dilakukan dengan broadcast. Broadcast adalah pesan langsung dapat dikirmkan tersebar yang diterima oleh seluruh komponen system yang sedang aktif.
Terdapat beragam tipe broadcast, yaitu:
- Reliable broadcast
- fifo broadcast
- Causal broadcast
- atomic broadcast
- Fifo atomic broadcast
- Causal atomic broadcast
Reliable broadcast
Tiga property reliable broadcast, yaitu:
- jika satu pesan benar mem- broadcast pesan m, maka semua proses benar memperoleh pesan yang dihantarkan. (Properti validity).
- Jika satu pesan benar memperoleh pesan m, maka semua proses benar mempunyai pesan m. (property agreement).
- untuk sembarang pesan m, tiap proses benar memperoleh pesan ,m tepat paling banyak sekali, dan hanya jika pesan m sebelumnya di- broadcast Pengirim pesan m.
Reliable broadcast merupakan tipe broadcast paling lemah. Tipe ini mungkin telah memadai untuk beberapa aplikasi. Reliable broadcast tidak menjamin urutan pesan yang dihantarkan. Pada beberapa aplikasi urutan pesan adalah penting. Pengurutan pesan terjamin pada FIFO broadcast.
FIFO Broadcast
FIFO broadcast menjamin pesan-pesan yang di-broadcast pengirim yang sama dihantarkan sesuai urutan pesan-pesan itu dihantarkan.
Maksud terurut FIFO (FIFO order)
Jika proses mem-broadcast pesan m sebelum proses itu mem-broadcast pesan m, maka tidak ada proses benar (tidak mengalami kegagalan) yang memperoleh m' kecuali sebelumnya memperoleh m.
Causal Broadcast
Causal Broadcast lebih kuat disbanding FIFO broadcast, yaitu pesan-pesan yang dihantarkan mengikuti relasi keterdahuluan sebab (Causal Broadcast). Konsep penting di system tersebar. Jika proses menghantarkan pesan m dan kemudian mem-broadcast m yang dapat bergantung" pada penghantaran pesan m sebelumnya, maka Causal Broadcast menjamin mengantarkan pesan m sebelum mengantarkan pesan m Causal Broadcast membolehkan proses mengantarkan pesan-pesan yang tidak terhubung sebab dalam urutan-urutan berbeda.
Maksud terurut sebab (Causal Broadcast)
Jika broadcast pesan m mendahului secara sebab broadcast pesan m, maka tidak ada pesan yang memperoleh pesan m kecuali sebelumnya memperoleh pesan m.
Atomic Broadcast
adalah mem-broadcast semua pesan secara terurut total.
Maksud terurut total (total arder)
Jika proses p dan q keduanya mengantarkan pesan m dan m , maka p mengantarkan m sebelum m jika dan hanya q mengantarkan m sebelum m.
Fifo Atomic Broadcast
FIFO atomatic broadcast adalah FIFO broadcast yang pesan-pesannya terurut secara total.
Causal Atomic Broadcast
Causal atomic broadcast adalah causal broadcast yang pesan-pesannya terurut secara totol.
Keterhubungan Tipe-Tipe Broadcast
Skema Hubungan Tipe-tipe Broadcast
Sehingga:
- Reliable broadcast = balidaty + agreement + integrity
- FIFO broadcast = reliable roadcast + FIFO order
- Causal broadcast = reliable roadcast + causal order
- Atomic broadcast = reliable roadcast + total order
- FIFO atomic broadcast = reliable roadcast +FIFO order + total order
- Causal atomic broadcast = reliable roadcast + causal order + total order.
Causal atomic broadcast memenuhi syarat causal order dan total order, lebih kuat disbanding FIFO atomic broadcast. Causal atomic broadcast merupakan mekanisme pokok pendekatan state-machine pada system fault-tolerance.
Timed Broadcast
Banyak aplikasi memerlukan pesan karakteristik berikut. Bila pesan dihantarkan semuanya, pesan dihantarkan dalam suatu waktu terbatas setelah sesan di-broadcast. Properti ini disebut Δ Timeliness.
Pada system tersebar, waktu yang dihabiskan dapat diinterpretasikan dalam dua cara barbeda yaitu:
- waktu nyata diukur oleh pengamat eksternal
- waktu local diukur oleh clock local proses-proses
(Real-time)Δ - Timeliness Broadcast
Terdapat konstanta Δ sehingga jika broadcast dari pesan m yang diinisilisasi pada waktu nyata t, tidak ada proses benar yang memperoleh pesan m setelah waktu nyata t + Δ
(Local-time)Δ - Timelines Broadcast
Terdapat konstanta Δ sehingga jika broadcast dari pesan m yang diinisialisasi pada waktu nyata t, tidak ada proses benar p yang memperoleh pesan m setelah waktu local ts(m) + Δ pada clock p.
Pada system asinkron, tidak ada algoritma reliable broadcast yang memenuhi real-time Δ - timeliness atau local-time Δ timeliness. Timed broadcast tidak dapat diimplementasikan.
Pada system sinkron, dapat diimplementasikan reliable broadcast yang memenuhi local-time timeliness. Tidak ada reliable broadcast yang dapat memenuhi real-time Δ timeliness pada system yang mempunyai kegagalan pewaktuan (timing failure).
4. Uniform Broadcast
Uniform agreement
Jike satu proses (yang benar atau yang mengalami kegagalan) mengantarkan pesan m, maka semua proses benar memperoleh pesan m.
Uniform Integrity
Untuk sembarang pesan m, setiap proses (yang benar atau yang mengalami kegagalan) mengantarkan pesan m paling banyak sekali, dan hanya jika suatu proses mem-broadcast pesan m.
Uniform Local-Time Δ - Timeline
Terdapat konstanta Δ yang diketahui sehingga tidak ada proses p ( yang benar atau yang mengalami kegagalan) mengantarkan pesan m setelah waktu local ts(m) + Δ pada clock p.
Uniform FIFO Order
Jika satu proses mem-broadcast pada pesan m sebelum proses mem-broadcast pesan m',maka tidak ada proses (yang benar atau mengalami kegagalan) mengantarkan m', kecuali proses sebelumnya memperoleh m.
Uniform Causal Order
Jika mem-broadcast pasan m mendahului secara sebab mem-broadcast pesan m', maka tidak ada proses (yang benar atau yang mengalami kegagalan) mengantarkan m sebelum m jika dan hanya jika q mengantarkan m.
Uniform Total Order
Jika sembarang p dan q (yang benar atau yang mengalami kegagalan),keduanya mengantarkan pesan m dan m, maka p mengantarkan m sebelum m jika dan hanya jika q mengantarkan m sebelum m.
Uniform timed reliable broadcast memenuhi proerti validaty, uniform agreement, uniform integrity dan uniform Δ -timeliness. Tipe ini digunakan untuk menyelesaikan masalah non-blocking atomic commitment problem.
Terminating Reliable Broadcast (TRB)
TRB adalah tipe broadcast yang proses-proses benar selalu memperoleh pesan -- meskipun pengirim mengalami kegagalan, atau crash sebelum mem-broadcast. Pesan yang dihantarkan dapat berupa pesan khusus SF € M yang menandai pengirim benar. Himpunan pesan yang dapat dikirim adalah M U {SF}.
Property TRB serupa dengan reliable broadcast, kecuali penambahan property termination:
- setiap proses benar memperoleh suatu pesan. (Properti termination).
- jika satu pesan benar mem-broadcast pesan m, maka semua proses benar memperoleh pesan yang dihantarkan. (property validity)
- jika satu pesan benar memperoleh pesan m, maka semua proses benar m memperoleh pesan m.(Properti agreement).
- untuk sembarang pesan m, tiap proses benar memperoleh pesan m tepat paling banyak sekali, dan jika memperoleh pesan m =SF maka pengirim mem-broadcast pesan m.
TRB dipelajari secara ekstensif dalam kasus arbitrary failure pada masalah Byzantine Agreement Problem atau Byzantine Generals Problem.
TRB berarti proses benar memperoleh pesan SF hanya jika pengirim mengalami kegagalan.
Consesus
Pada TRB, satu proses tunggal dimisalkan mem-broadcast pesan dan semua proses benar harus sepakat denagn pesan itu. Pada masalah consensus,semua proses benar mengusulkan (propose) satu nilai dan harus bersepakat dengan suatu nilai yang berhubungan dengan nilai yang diusulkan.
Primitive di masalah konsesus.
Dimana v adalah suatu nilai.
Propose (v)
Saat satu proses menjalankan propose (v), berarti prose situ mengusulkan v.
Decide (v)
Saat satu proses menjalankan decide(v), berarti proses memutuskan v.
V adalah himpunan semua nilai yang dapat diusulkan. Himpunan semua nilai yang dapat diputuskan adalah V U {Nu}, dimana NU E V. NU merupakan nilai khusus yang menandai bahwa tidak semua proses mengusulkan nilai yang sama. NU singkatan dari no unanimity.
Spesifikasi masalah konsesus:
- Setiap proses benar memutuskan suatu nilai. (Properti terminator).
- Jika semua proses yang mengusulkan satu nilai. Mengusulkan v, maka semua proses benar memutuskan nilai v. (Properti validaty).
- Jika satu proses benar memutuskan nilai v , maka semua proses benar memutuskan nilai v. (Properti agreement)
- Setiap proses benar memutuskan paling banyak satu nilai, dan jika proses memutuskan v = NU maka suatu proses harus telah mengusulkan v.
Properti lebih kuat
Strong validity
Jika semua proses benar mengusulkan nilai v, maka semua proses benar memutuskan nilai v.
Strong integrity
Setiap proses benar memutuskan paling banyak satu nilai, dan jika proses memutuskan nilai v, maka suatu proses harus telah memutuskan nilai v.
Proses benar tidak pernah memutuskan NU. Meskipun terdapat NU di nilai yang diusulkan.
Ketidakmungkinan consensus di system asinkron, tidak ada algoritma deterministic yang dapat menyelesaikan masalah consensus di system asinkron dan mentoleransi bahkan satu kegagalan crash tunggal.
Implementasi Komunikasi Kelompok
Implementasi primitive komunikasi kelompok:
- Multicasting
- Broadcasting
- Unicasting
Jika jaringan tidak menyediakan mekanisme multicasting atau broadcasting, maka komunikasi kelompok diimplementasikan dengan mengirim paket terpisah ke tiap anggota. Meski tidak efisien, implementasi ini masih dapat dilakukan khususnya pada kelompok kecil. Pengiriman satu pengirim ke satu penerima disebut unicasting.
Pilihan dalam perancangan komunikasi kelompok:
- Pemilihan primitive blocking atau non-blocking.
- Pemilihan primitive buffer dan tak di buffer.
