SISTEM TERDISTRIBUSI Coordination and Agreement
Disusun Oleh: 1. Eldest Arif Pasirula
33220
2. Udi Hartono
33317
3. Arif Febriyanto
33451
Jurusan Teknik Elektro Fakultas Teknik Universitas Gadjah Mada
2 0 0 9
Coordination dan Agreement Arif Febriyanto, 33451 Eldest Arif Pasirula, 33220 Udi Hartono, 33317 Jurusan Teknik Elektro FT UGM, Yogyakarta
1. PENDAHULUAN Dalam makalah ini akan memperkenalkan sekumpulan algoritma yang tujuannya berbeda-beda tetapi menjadi bagian dalam tujuan dasar sistem terdistribusi, yaitu satu set proses untuk mengkoordinasikan tindakannya atau untuk setuju pada satu atau lebih nilai. Contohnya pada kasus mesin seperti pesawat ruang angkasa. Hal itu perlu dilakukan, komputer mengendalikannya agar setuju pada kondisi tertentu seperti apakah misi dari pesawat luar angkasa dilanjutkan atau telah selesai. Komputer tersebut harus mengkoordinasikan tindakannya secara tepat untuk berbagi sumber. Lebih jauh, komputer harus dapat melakukan seseuatu bahkan jika tidak ada hubungan master-slave yang belum jelas diantara komponen dan akan membuat koordinasi menjadi sederhana. Hal yang penting dalam Coordination and Agreement adalah apakah sistem terdistribusi asinkron atau sinkron. Algoritma –algoritma yang digunakan juga harus mempertimbangkan kegagalan yang terjadi, dan bagaimana caranya untuk berhubungan satu sama lain ketika sedang mendesaian algoritma. Selanjutnya di makalah ini juga akan dijelaskan mengenai masalah dalam mendistribusikan mutual exclusion, election, multicast communication, dan mengenai masalah dalam persetujuan(agreement).
Gambar crashed router pada network portion Perbaikan-perbaikan dijelaskan pada bab ini dengan melibatkan asumsi-asumsi dan tujuan yang harus dipenuhi, dan memberikan akun informal mengapa algoritma yang disajikan benar. 1.1 Asumsi Kegagalan (Failure Assumption) dan Pendeteksi Kegagalan (Failure Detectors) Sebelum membicarakan tentang masalah dalam Coordination and Agreement , terlebih dahulu menjelaskan tentang asumsi kegagalan dan keadaan yang berguna dalam mendeteksi kegagalan pada sistem terdistribusi. Dalam interval waktu tertentu, komunikasi diantara beberapa proses dapat berlangsung ketika komunikasi diantara lainnya ditunda. Salah satu masalah dalam pembuatan algoritma yang bisa menyebabkan terjadinya crash adalah bila terjadi proses crash itu sendiri. Failure Detector adalah suatu layanan yang mempertanyakan apakah proses
yang terjadi gagal atau tidak. Failure Detector kadang tidak tepat. Kebanyakan kegagalannya adalah pada failure detector yang tidak handal, yang bisa menghasilkan hal yang diduga maupun tidak terduga. Kedua hasil tersebut merupakan petunjuk yang menggambarkan keakuratan atau ketidakakuratan apakah suatu proses benar-benar gagal. Hasil yang tidak terduga berarti pendeteksi telah menerima fakta-fakta bahwa proses tidak gagal. Kemudian hal yang diduga berarti failure detector memiliki beberapa indikasi yang menyatakan bahwa proses itu gagal. Failure Detector yang handal merupakan salah satu pendeteksi kegagalan yang paling akurat. Ia menjawab proses pertanyaan salah satu dari yang tidak terduga, seperti sebelumnya, mendapat petunjuk atau gagal. Failure detector kadang-kadang dapat memberikan respon yang berbeda jika kondisi komunikasi bermacam-macam dari proses ke proses. Dalam sistem terdistribusi nyata, terdapat batasan tertentu dalam waktu pengiriman pesan. Batasan ini disebut dengan time out. Jika kita memilih nilai total time out yang besar, maka proses akan crash dan akan dilaporkan sebagai Unsuspected. Solusi yang mungkin untuk masalah ini adalah dengan menggunakan nilai time out yang mencerminkan kondisi network delay yang telah diamati. Failure detector digunakan karena dapat membantu untuk mencari dan mengetahui sebab terjadinya kegagalan pada sistem terdistribusi. Sehingga kita dapat mencari solusi yang tepat untuk memecahkan masalah tersebut dalam hal pengkoordinasian proses jika terjadi kegagalan. 2. DISTRIBUTED MUTUAL EXCLUSION Distributed mutual exclusion dibutuhkan jika sekumpulan proses bersama-sama menggunakan sumber untuk mencegah gangguan dan menjaga konsistensi ketika sedang mengakses sumber. Karena jika tidak, masalah crtical section akan terjadi, masalah yang sering terjadi pada domain pada sistem operasi. Pada sistem terdistribusi, tidak ada satupun variabel yang dipakai secara bersama-sama maupun fasilitas yang diberikan melalui lokal kernel tunggal bisadigunakan untuk memecahkan hal tersebut. Dalam beberapa kasus, sharing sesumber diatur oleh server yang juga menyediakan mekanisme untuk mutual exclusion. Namun, dalam beberapa kasus tertentu mekanisme yang terpisah untuk mutal exclusion sangat diperlukan. Untuk lebih jelas lagi, misalnya ada seorang user yang ingin melakukan update pada file text. Untuk memastikan updatan milik user tersebut berjalan dengan konsisten maka hanya boleh dilakukan satu update aja untuk saat itu sehingga dibutuhkan editor lock sebelum melakukan update. System UNIX menyediakan service file locking yang terpisah yang diimplementasikan oleh daemon locked yang berfungsi untuk menghandle locking request dari client. Sangat berguna untuk memiliki mekanisme umum untuk didistribusikan mutual exclusion pada penyelesaian yang independen dari skema manajemen sumber daya tertentu masih dalam pertanyaan. Kita sekarang meneliti beberapa algoritma untuk mencapai itu. 2.1 Algoritma untuk Mutual Exlusion Algoritma mutual Exclusion membutuhkan beberapa syarat, yaitu: 1. Keamanan( safety), hanya satu proses yang dieksekusi pada satu waktu, 2. Liveness, meminta untuk masuk dan keluar dari critical section yang secepatnya menggantikan. Kondisi liveness menyatakan kebebasan dari keduanya , deadlock dan starvation. Deadlock akan melibatkan dua atau lebih program yang dalam keadaan saling tunggu. Starvation adalah penundaan suatu proses yang telah memintanya. 3. Ordering, akses diterima dan terjadi sebelum relasi, dengan begitu proses dapat berkoordinasi.
Proses dapat menunggu akses dan berkomunikasi dengan proses lainnya. Untuk mengevaluasi performa dari algoritma mutual exclusion dapat dilihat dari: 1. Bandwith digunakan sebanding dengan jumlah pesan yang dikirim pada setiap masuk atau keluar dari C.S (Critical Section). 2. Client Delay terjadi setiap operasi entry and exit. 3. Throughput, efek dari algoritma atas throughput pada sistem.
Server mengatur Mutual Exclusion Token Kita seharusnya tidak melakukan implemtasi akses sesumber ke dalam akun dalam deskripsi kita. Kita mengasumsikan bahwa proses klien adalah langkah yang tepat dan menghabiskan waktu akses sesumber yang terbatas dengan crital section mereka. 2.1.1 Algoritma Server Terpusat Cara yang paling mudah untuk mencapai mutual exclusion adalah dengan memperkerjakan sevet yang menanggung ijin untuk memasuki critical section. Untuk masuk ke critical section, proses harus mengirim request message kepada server dan menunggu balasan dari server. Server membalas message tersebut mengikuti token. Namun jika tidak ada request pada token tersebut selain dari proses itu maka prose situ akan segera diberi replay message. Memasuki critical section, bahkan ketika tidak ada proses yang saat ini menempati itu. Dua pesan palsu), dan penundaan proses yang meminta waktu untuk pulang-pergi. Keluaran bagian kritis mengambil satu pesan keluaran. Dengan asumsi lewat pesan asynchronous, hal ini tidak menunda proses keluar. Server mungkin menjadi hambatan untuk perfoma sistem secara keseluruhan. Tunda sinkronisasi adalah waktu yang dibutuhkan untuk pulang-pergi: 8 rilis pesan ke server, diikuti oleh pesan grant ke proses selanjutnya masukkan critical section. 2.1.2 Algoritma Ring-based Cara yang paling mudah dalam perangkai mutal excluison diantara N proses ranpa membutuhkan proses tambahan untuk merangkainya dalam logical ring.
Ring processing mutual exclusion token Algoritmanya sebagai berikut : On inilization : State := RELEASED; To Enter Section : State := WANTED; Multicast request to all process; T := request’s timestamp; Wait until (Number of replies received = (N-1)); State := HELD; On receipt of a request <Ti,Pi> at Pj (i≠j) If (State = HELD or (state = WANTED and (T,Pj) < (Ti,Pi))) Then Queque request from Pj without replaying; Else Replay immediately to Pj; End if To exit the critical section : State := RELEASED; Replay to any quequed request;
Jika proses tidak memerlukan masukan ke critical section ketika menerima token, kemudian segera meneruskan ke token tetangganya. Sebuah proses yang memerlukan oken menunggu sampai diterima, namun menahannya. Untuk keluar dari critical section, proses mengirim token ke tetangganya. Algoritma ini mengkonsumsi bandwidth dari jaringan, kecuali ketika proses berada pada bagian dalam critical section. 2.1.3 Algoritma menggunakan Multicast dan Logical Clock
Multicast atau multicasting adalah sebuah teknik di mana sebuah data dikirimkan melalui jaringan ke sekumpulan komputer yang tergabung ke dalam sebuah grup tertentu, yang disebut sebagai multicast group. Multicasting merupakan sebuah cara pentransmisian data secara connectionless (komunikasi dapat terjadi tanpa adanya negosiasi pembuatan koneksi), dan klien dapat menerima transmisi multicast dengan mencari di mana lokasinya, seperti halnya ketika kita membuka sebuah stasiun radio untuk mendengarkan siaran radio. Multicast sebenarnya merupakan mekanisme komunikasi one-to-many, atau point-tomultipoint, dan berbeda dengan cara transmisi unicast. Ide dasarnya adalah hanya ketika semua proses yang lain menjawab pesan. Setiap pesan direkam tiaptiap bagian luar dari critical section (released), wanting entry (wanted) atau dalam critical section (held) dalam variable state. Jika proses permintaan entri dan bagian semua proses-proses lain RELEASED, kemudian semua proses akan segera menjawab dengan segera kepada permintaan dan peminta akan memperoleh entri. Jika beberapa proses bagian HELD. maka proses itu tidak akan menjawab permintaan sampai selesai dengan crirical state. Jadi si peminta tidak dapat memperoleh entri untuk sementara. Jika dua atau lebih proses permintaan masuk pada saat yang sama, maka proses mana permintaan mengemban timestamp terendah akan menjadi yang pertama untuk mengumpulkan N - 1 balasan, pemberian itu entri berikutnya. Perhatikan bahwa. Ketika proses permintaan masuk, penangguhan pemrosesan permintaan dari proses-proses lain sampai permintaan sendiri telah dikirim dan telah mencatat timestamp T dari permintaan. Hal Ini agar proses membuat keputusan yang konsisten saat memproses permintaan. Kinerja algoritma dapat ditingkatkan. Pertama, perhatikan bahwa proses yang terakhir masuk ke bagian kritis dan yang tidak menerima permintaan lain untuk itu masih berlanjut melalui protokol seperti yang dijelaskan, walaupun hanya bisa memutuskan secara lokal untuk mengalokasikan kembali itu sendiri. Kedua, Ricart dan Agrawala menyaring protokol ini sehingga hanya memerlukan N pesan untuk mendapatkan masukasn dalam kasus yang paling parah tanpa dukungan hardware untuk multicast. Algoritma ini dideskribsikan oleh Raynal [1988]. 2.1.4 Algoritma Voting Maekawa Maekawa [1985] mengamati bahwa dalam pemesanan proses untuk memasukkan critical section, tidak penting semua pasangan untuk memberikan hak untuk mengaksesnya. Proses hanya memerlukan izin untuk masuk dari himpunan kawannya, sepanjang himpunan digunakan oleh 2 proses yang overlap.Proses dapat dianggap sebagai voting satu sama lain untuk masuk ke critical section. Kandidat proses harus mengumpulkan suara yang cukup untuk masuk. Proses dalam perpotongan 2 himpunan pemilih yang menyakinkan keamanan properti dari ME1, yang paling banyak 1 proses dapat masuk critical section. Algoritma Maekawa ditunjukkan di bawah ini: On il1itialization state := RELEASED; voted := FALSE; For P, to enter the cntical section state != WANTED; Multicast request to all processes in Vi - {Pi}; Wait until (number of replies received = (K - 1»; state := HELD; On receipt ofa request from PI at p. (i 01' j) If(state = HELD or voted = TRUB) then queue request from Pi without replying;
else send reply to Pi' voted:= TRUE; end!f For Pi to exit the critical section state := RELEASED; Multicast release to all processes in Vi - {Pi}; On receiptofa release from Pi at Pj (iol'j) If(queue of requests is non-empty) then remove head of queue - from Pk' say; send reply to Pk; voted := TRUE; else voted := FALSE; end if
Algoritma tersebut diadobsi [Saunders 1987] sehingga menjadi bebas deadlock. Dalam pengadopsian protokol, antrian prosesmeminta dalam pemesanan yang terjadi sebelumnya, sehingga permintaan terhadap ME3 juga memuaskan. 2.1.5 Toleransi Kesalahan Poin utama yang perlu dipertimbangkan ketika mengevaluasi algoritma di atas sehubungan dengan toleransi kesalahan adalah: ‐ Apa yang terjadi ketika pesan hilang? ‐ Apa yang terjadi ketika proses crash? Tak satu pun dari algoritma yang kita gambarkan akan menoleransi hilangnya pesan, jika saluran yang dapat diandalkan. Algoritma berbasis cincin tidak dapat menoleransi kegagalan crash setiap proses tunggal. Algoritma Maekawa dapat mentolerir beberapa proses kegagalan karena crash, jika proses crash tidak dalam menetapkan suara yang diperlukan, maka kegagalan akan tidak mempengaruhi proses lain. Algoritma server pusat dapat mentolerir kegagalan crash dari proses klien yang tidak berlaku atau telah diminta token. Algoritma The Ricart dan Agrawala seperti yang telah kita jelaskan dapat disesuaikan dengan mentolerir kegagalan crash proses, dengan mengambilnya untuk memberikan semua permintaan secara implisit. 3. ELECTIONS Sebuah algoritma untuk memilih proses unik untuk memainkan peranan tertentu disebut algoritma elections. Sebagai contoh, dalam sebuah varian dari kami algoritma ‘central-server' algoritma untuk mutual exclusion, server yang dipilih diantara proses P "j = 1,2 ..., N yang perlu untuk menggunakan critical section. Pemilihan algoritma diperlukan untuk memilih mana dari proses akan memainkan peran dari server. Sangat penting bahwa semua proses menyetujui pilihan. Setelah itu, jika proses yang memainkan peran server ingin berhenti, kemudian pemilihan lain yang diperlukan untuk memilih pengganti. Sebuah proses individu tidak menyebut lebih dari satu pemilihan umum pada suatu waktu, tetapi pada prinsipnya proses N bisa menelepon N bersamaan pemilihan. Pada setiap titik waktu, sebuah proses Pi adalah salah satu peserta, yang berarti bahwa itu terlibat dalam beberapa menjalankan pemilihan algoritma, atau non-peserta, yang berarti bahwa tidak saat ini terlibat dalam pemilihan. Persyaratan penting bagi pilihan proses terpilih untuk menjadi unik, bahkan jika beberapa proses pemilihan panggilan secara bersamaan. Misalnya. dua proses dapat memutuskan secara independen bahwa proses koordinator telah gagal, dan kedua panggilan pemilihan.
Tanpa kehilangan umum. kami mensyaratkan bahwa proses terpilih dipilih sebagai satu dengan pengenal terbesar. The 'identifier' mungkin ada nilai berguna. Sepanjang pengidentifikasi yang unik dan benar-benar memerintahkan. Sebagai contoh, kita dapat memilih proses dengan komputasi terendah beban, oleh karena setiap proses menggunakan
sebagai identifier, di mana beban> 0 dan proses indeks i digunakan untuk memesan pengidentifikasi dengan beban yang sama. Setiap proses Pi (i = saya, 2 ..., N) memiliki variabel terpilih, yang akan berisi identifier dari proses terpilih. Ketika proses pertama menjadi peserta dalam pemilihan itu set variabel ini (u nilai khusus '1 .-' untuk menunjukkan bahwa itu belum didefinisikan. Persyaratannya adalah bahwa, selama menjalankan algoritma tertentu adalah : E1 : (safety) A peserta proses pi mempunyai electedi = ┴ atau electedi = P dimana P dipilih sebagai proses yang tidak crash pada akhir dari penggunaan identifier terbesar. E2: (liveness) Semua proses pi ikut serta dan khususnya ditentukan electedi ≠ ┴ atau crash. Kami mengukur kinerja algoritma pemilihan oleh jaringan total pemanfaatan bandwidth (yang sebanding dengan jumlah pesan yang dikirim), dan oleh waktu penyelesaian untuk tbe algoritma: jumlah pesan transmisi serial antara inisiasi dan penghentian single run. 3.1 Algoritma Pemilihan Ring-Based Tujuan dari algoritma ini adalah untuk memilih sebuah proses tunggal yang disebut koordinator, yang merupakan proses dengan identifier terbesar. Awalnya, setiap proses ditandai sebagai non-peserta dalam pemilihan. Setiap proses bisa mulai pemilihan. Hal hasil dengan menandai dirinya sebagai salah satu peserta, menempatkan para identifier dalam pemilihan pesan dan mengirimkannya kepada tetangga searah jarum jam. Ketika sebuah proses menerima pesan pemilihan, itu membandingkan pengenal dalam pesan dengan sendiri. Jika identifier yang tiba lebih besar, maka meneruskan pesan 10 tetangganya. Jika identifier yang tiba lebih kecil dan penerima bukan merupakan peserta maka pengganti pengenal sendiri dalam pesan dan ke depan itu, tetapi tidak meneruskan pesan jika sudah menjadi peserta. Pada pemilihan penerusan pesan dalam beberapa kasus, proses menandai dirinya sebagai peserta.
Pemilihan dimulai dari proses 17. Proses identifier tertinggi yang ditemukan setelah itu adalah 24. Peserta proses ditunjukkan pada bagian gelap.
Namun, jika identifier yang diterima adalah dari penerima itu sendiri, maka proses ini pengenal harus menjadi yang terbesar, dan itu menjadi koordinator. Koordinator tanda dirinya sebagai non-peserta sekali lagi dan mengirim pesan terpilih ke tetangga, mengumumkan pemilihan dan melampirkan identitasnya. Ketika sebuah proses PI menerima pesan terpilih, itu menandai dirinya sebagai nonpartisipan, menetapkan variabel yang dipilih, untuk pengenal dalam pesan dan, kecuali jika itu adalah koordinator baru, meneruskan pesan kepada tetangganya. Sangat mudah untuk melihat bahwa E1 kondisi tersebut dipenuhi. Semua pengidentifikasi dibandingkan, karena seorang proses harus menerima identifier sendiri kembali sebelum mengirim pesan terpilih. Untuk setiap dua proses, yang satu dengan identifier yang lebih besar akan tidak lulus pada identifier lain. Oleh karena itu, tidak mungkin bahwa kedua harus menerima identifier mereka sendiri. Kondisi E2 berikut dijamin langsung dari cincin traversals (tidak ada kegagalan). Perhatikan bagaimana non-participalll dan negara-negara peserta digunakan begitu pesan yang timbul ketika proses lain mulai pemilihan pada waktu yang sama adalah dipadamkan sesegera mungkin, dan selalu sebelum 'menang' hasil pemilihan telah diumumkan. Jika hanya satu proses memulai pemilihan, maka kasus yang berperforma terburuk adalah ketika anti-clockwise tetangga memiliki identifier paling tinggi. Contoh sebuah cincin berbasis pemilihan berlangsung ditunjukkan pada gambar diatas. Itu pesan pemilihan saat ini mengandung 24, tetapi proses 28 akan menggantikan dengan identifier bila pesan mencapainya. 3.2 The Bully Algorithm Adalah (Gracia-Moliana 1982) algoritma yang mengijinkan proses mengalami crash pada saat terjadi pemilihan (election), meskipun pengiriman pesan antar proses adalah reliable.Ada tiga tipe pada algoritma ini, yaitu: 1. election message : digunakan untuk pemberitahuan akan adanya pemilihan 2. answer message : merupakan jawaban dari election message 3. coordinator message : digunakan untuk memberitahukan identitas dari proses pemilihan Sebuah proses dimulai dengan pemilihan ketika telah diperintahkan, melewati timeout, saat coordinator gagal. Ketika sebuah proses menerima pesan coordinator proses tersebut akan menset variabelnya menjadi elected. Jika sebuah proses menerima proses election proses tersebut akan mengirim jawaban dan akan memulai proses terpilih tersebut, kecuali telah mulai sebelumnya. 4. MULTICAST COMMUNICATION Fitur penting dari multicast adalah bahwa permasalahan pokok proses hanya satu operasi multicast yang digunakan untuk mengirim untuk tiap kelompok proses. Penggunaan satu operasi multicast bukannya jumlah beberapa operasi mengirim ke lebih dari kenyamanan bagi para pemrogram. Ini memungkinkan implementation menjadi efisien dan memungkinkan untuk memberikan jaminan pengiriman kuat daripada yang lain mungkin. Efisiensi: Informasi pesan yang sama dikirim kepada semua proses dalam kelompok memungkinkan pelaksanaannya efisien dalam penggunaan bandwidth.Hal ini dapat mengambil langkah-langkah untuk mengirim pesan tidak lebih dari satu kali selama hubungan komunikasi berlangsung, dengan mengirimkan
pesan melalui distribusi tree; dan dapat menggunakan perangkat keras jaringan yangdapat mensupport multicast.Pelaksanaan juga dapat meminimalkan total waktu yang dibutuhkan untuk menyampaikan pesan ke semua tujuan, lebih dari transmisi secara terpisah dan serial. Menjamin pengiriman: Jika isu proses beberapa operasi mengirim independen proses individu, maka tidak ada jalan bagi pelaksanaan untuk memberikan pengiriman menjamin bahwa kelompok mempengaruhi proses secara keseluruhan. Jika pengirim gagal setengah jalan melalui pengiriman. kemudian beberapa anggota kelompok mungkin menerima pesan sementara yang lainnya tidak. Dan relatif ordenng dari dua pesan disampaikan kepada setiap dua anggota kelompok is undefined. Dalam kasus khusus IP multicast, tidak ada jaminan kehandalan memesan atau sebenarnya ditawarkan. Tapi multicast jaminan yang lebih kuat dapat dibuat, dan kita akan segera menetapkan beberapa. 4.1 Basic Multicast Suatu hal yang jelas pada implementasi dari B-multicast adalah untuk menggunakan operasi one-to-one yang reliable. Sepeti contoh berikut: To B-multicast(g,m): foreach process p g, send(p,m) On receive(m) at p: B-deliver(m) at p Layanan b-multicast yang lebih praktikal dapat dibangun menggunakan IP multicast. 4.2 Reliable Multicast Mengikuti pendapat Hadzilacos dan Toueg, dan Chandra dan Toueg kita dapat mendefinisikan reliable multicast. Sebuah reliable multicast memiliki properti seperti: integrity, validity, agreement. 4.2.1 Implementasi Reliable Multicast Terhadap B-multicast Algoritma ini cocok diterapkan pada asynchronus sistem, tapi tidak cocok diterapkan pada tujuan praktis. Hal ini dikarenakan stiap pesan mengirim |g| kali untuk tiap proses. 4.2.2 Reliable Multicast terhadap IP Multicast Realisasi alternatif R-multicast adalah menggunakan kombinasi IP multicast. Protokol R-multicast ini berdasar pada IP multicast. Pada protokol proses tidak mengirim pesan ack secara terpisah, melainkan pada sebuah grup. 4.2.3 Properti Seragam Properti apapun yang menahan apakah proses benar atau tidak dinamakan uniform property. Pemahaman uniform sendiri yaitu: jika sebuah proses, tidak peduli benar atau tidak, mengirim pesan m, kemudian semua proses yang benar pada group(m) akan secepatnya mengirim m. 4.3 Ordered Multicast 4.3.1 Contoh Buletin Board Untuk membuat semantik pengiriman multicast lebih konkrit, perlu mempertimbangkan sebuah aplikasi dimana user mem-post pesan pada buletin board. 4.3.2 Implementasi Perintah FIFO
Implementasi B-multicast dapat digunakan pada protokol ini, namun R-multicast dapat menjadikan FIFO-multicast lebih stabil. 4.3.3 Implementasi Perintah Total Algoritma ini memiliki latensi yang lebih tinggi daripada multicast berdasar sequence. Namun total ordering yang dipilih algoritma ini tidak menjamin menjadi biasa atau pun FIFO-ordered, tergantung pada pengaruh delay komunikasi. 4.3.4 Implementasi Perintah Kausal Algoritma ini diterapkan pada non-overlapping gup tertutup yang berdasarkan pada algoritma yang dikembangkan oleh Birman et al. Algoritma ini memerlukan account dari hubungan terjadi-sebelumnya saja seakan itu telah didirikan menggunakan pesan multicast. 4.3.5 Pelengkapan Grup Sebelumnya kita telah memperhitungkan grup non-overlapping di dalam definisi dan algoritma FIFO, total dan pengururtan kausal semantik. Hal ini menyederhanakn masalah, akan tetapi tidak memuaskan, selama proses umumperlu menjadi anggota grup overloping. Kita bisa mengembangkan definisi pengurutan menjadi urutan global , dimana kita harus memperhitungkan bahwa pesan m adalah multicast ke g dan jika pesan m’ adalah multicast ke g’, kemudian kedua pesan dialamatkan ke anggota g n g. Pengurutan FIFO global: Jika sebuah proses memberikan multicast(g,m) dan kemudian multicast(g’,m’) kemudian setiap proses di g n g’ yang menyampaikan m’ akan menyampaikan m sebelum m’. Pengurutan Kausal Global: Jika multicast (g,m) Æ multicast (g’,m’)dimana terjadi sebelum hubungan didorong oleh rantai pesan multicast, kemudian proses dalam g n g’ yang menyampaikan m’ akan menyampaikan m sebelum m’. Pengurutan Total Pairwise: Jiak sebua proses menyampaikan m dikirim ke g sebelum menyampaikan m’ ke g’, kemudian proses lain di dalam g n g’ yang menyampaikan m’ akan menyampaikan m sebelum m’. Pengurutan Total Global: ‘<’ menjadi relasi pengurutan antara waktu penyampaian. Kita menyatakan bahwa ‘<’ sesuai dengan pengurutan total pair wise. 4.3.6 Multicast di dalam sistem sinkron dan asinkron. Dalam bab ini kita telah mendiskudsikan algoritma untuk kehandalan multicast tak terurut, multicast FIFO-terurut, multicast terurut kausal dan multicast terurut total. Kita juga ditunjukkan bagaimana menyelesaikan sebuah multicast terurt total sekaligus kausal. Algoritma-algoritma yang telah ditunjukkan sebelumnay adalah algoritma yang mampu bekerja secara benar dalam sistem asinkron. 5 KONSENSUS DAN MASALAH-MASALAH YANG TERKAIT Bab ini memperkenalkan permasalahan konsensus dan masalah terkait dengan byzantine generals dan konsistensi interaktif. Bab ini menjelaskan konsensus lebih jelas dan menghubungkannya dengan tiga masalah persetujuan yang terkait: byzantine generals, konsistensi interaktif dan multicast terurut total. Kita
bisa memulai memeriksa cirkum permasalahan apa yang dapat dipecahkan dan menggambarkan beberapa solusi. 5.1 Model sistem dan Definisi Permasalahan. Model sistem kita termasuk koleksi proses pi (i=1,2,3,.....,N) pengominikasian oleh pelewat pesan. Kebutuhan penting yang banyak diaplikasikan dalam situasi praktik adalah untuk menjadikan konsensus tercapai bahkan saat adanya kesalahan. Kita asumsikan, seperti sebelumnya, bahwa komunikasinya handal, akan tetapi prosesnya mungkin gagal.
Konsensus untuk tiga proses 5.1.1 Definisi permasalahan konsensus. Untuk mencapai konsensus, setiap proses pi mulai di dalam keadaan yang tak tentu dan mengusulkan sebuah nilai vi, dari satu set D (i=1,2,.....,N). Proses-proses yang ada saling berkomunikasi, bertukas nilai. Setiap proses selanjutnya mengatur nilai decision variable di. Saat melakukan ini, maka masuk dalam keadaan yang tertentu, dimana mungkin tak ada lagi perubahan di (i=1,2,.....,N). Gambar diatas menunjukkan tiga proses yang terikat dalam suatu algoritma konsensus. Dua proses mengusulkan ‘proceed’ dan yang ketiga mengusulkan ‘abort’ tetapi kemudian bertabrakan. Kemudian dua proses yang tersisa memutuskan ‘proceed’. Kebutuhan dari algoritma konsensus adalah kondisi berikut yang seharusnya berlangsung untuk setiap eksekusi : • Termination. Saat dimana setiap proses diset variabel-tentunya. • Agreement. Nilai tertentu dari semua proses adalah sama. Jika pi dan pj adalah benar dan telah masuk dalam keadaan tertentu, maka di=dj (i,j = 1,2,.....,N). • Integrity. Jika proses yang benar semua mengusulkan nilai yang sama, maka setiap proses dalam keadaan tertentu telah memilih nilai tersebut. 5.1.2 Permasalahan Byzantium General Permasalahan Byzantium General berbeda dari konsensus. Kebutuhannya adalah • Termination. Saat dimana setiap proses yang benar mengatur variabel tertentunya.
• •
Agreement. Nilai tertentu dari semua proses adalah sama. Jika pi dan pj adalah benar dan telah masuk dalam keadaan tertentu, maka di=dj (i,j = 1,2,.....,N). Integrity. Jika pemerintah (commander) benar, maka semua proses menentukan nilai pada nilai yang diusulkan commander.
5.1.3 Konsistensi Intersktif. Permasalahan konsistensi interaktif adalah varian lain dari konsensus, dimana setiap proses mengusulkan nilai tunggal. Tujuan dari algoritma adalah membenahi proses agar setuju dalam sebuah vektor nilai, satu untuk setiap proses. Kita menyebutnua ‘decision vector’. Kebutuhan untuk konsistens interaktif adalah: • Termination. Saat dimana setiap proses yang benar mengatur variabel tertentunya. • Agreement. Vector putusan dari semua proses adalah sama. • Integrity. Jika pi benar, maka semua proses memutuskan vi sebagai komponen ke i dari vektor mereka. 5.1.4 Keterkaitan Konsensus dengan Permasalah Lain. Terkadang dimungkinkan menemukan suatu solusi dari sebuah solusi permasalahan lain. Anggap bahwa terdapat solusi untuk konsensus (C), byzantine general (BG) dan konsistensi interaktif (IC) sebagai berikut: • Ci (v1,v2,.....vN) mengembalikan nilai putusan pi di dalam penggunaan solusi dalam permasalahan konsensus, dimana v1, v2, ...... vN adalah yang diusulkan proses. • BGj (j,v) mengembalikan nilai putusan dari pj dalam penggunaan solusi dalam permasalahan byzantine general dimana pj, commander, mengajukan nilai v. • Ici(v1,v2,....vN)[j] mengembalikan nilai ke j didalam vektor pj dalam menjalankan solusi permasalahan konsistensi intersktif, dimana v1, v2,.... vN adalah nilai yang diusulkan proses. 5.2 Konsensus Dalam Sistem Asinkron Algoritma konsensus dalam sistem sinkron misalnya sebagai berikut : Algorithm for process Pj € g; algorithm proceeds in f + I rounds On initialiration 0 Values,:== {vi}; Values! == {}; In round r (l ≤ r ≤ f + 1) B-multi,cast(g, Valuerj - Value i r-1 // Send only values that have not been .sent Valueir+1 := Valuesi; while (in round r) { On B-deliver( V).) from some P , Values i :== Values! u Vj; } After (f + 1) rounds Assign di = minimum(Valuesif+1);
5.3 Permasalahan Byzantine General dalam Sistem Sinkron
5.3.1 Ketidakmungkinan dalam Sistem Asinkron Terdapat ketidakmungkinan dalam sistem asinkron, yaitu : Menyembunyikan kesalahan Konsensus penggunaan detektor kesalahan Konsensus penggunaan pengacakan 6. KESIMPULAN
Salah satu masalah dalam pembuatan algoritma yang bisa menyebabkan terjadinya crash adalah bila terjadi proses crash itu sendiri. Failure Detector [Chandra and Toueg 1996, Stelling et al. 1998] adalah suatu layanan yang mempertanyakan apakah proses yang terjadi gagal atau tidak. Failure detector dapat membantu kita untuk mengetahui sebab-sebab terjadinya kegagalan pada sistem terdistribusi. Jika sekumpulan proses bersama-sama menggunakan sumber, mutual exclusion dibutuhkan untuk mencegah gangguan dan menjaga konsistensi ketika sedang mengakses sumber. Algoritma yang digunakan untuk memilih proses unik untuk memainkan fakta-fakta disebut election alghoritm. Multicast atau multicasting adalah sebuah teknik di mana sebuah data dikirimkan melalui jaringan ke sekumpulan komputer yang tergabung ke dalam sebuah grup tertentu, yang disebut sebagai multicast group. Beberapa algoritma yang terkait pada Coordination & Agreement diantaranya adalah: 1. Ring Based Alghoritm 2. Algoritma Koordinasi 3. Centralized Mutual Exclusion 4. Multicast Mutual Exclusion 5. Chang&Robert alghiritm 6. Richart – Agrawala Alghoritm Algoritma konsensus digunakan ketika persetujuan dibutuhkan pada tindakan : – Pada proses transaksi Menjalankan atau mengakhiri transaksi – Mutual Exclusion Prsoes mana yang boleh masuk C.S(Critical Section) – Pada Sistem Kontrol Meneruskan atau mengakhiri berbasis pada pembacaan sensor
Byzantine Generals merupakan proses penampilan dari kegagalan, bergantung kepada f dari N preoses kegagalan.
REFERENCE [1] Coulouris George, Jean Dollimore, Tim Kindberg. Distributed System Concepts and Design:Addison Wesley [2] http://te.ugm.ac.id/%7Erisanuri/v01/wp-content/uploads/2009/06/koordinasi_agreement01.pdf, retrieved 17 Desember 2009
