COORDINATION AND AGREEMENT

Muhammad Bayu Utama, 32503 Yodhi Kharismanto, 32552

Jurusan Teknik Elektro FT UGM, Yogyakarta

I. INTRODUCTION

Coordination and Agreement, dalam makalah ini kami akan menjelaskan sekumpulan algoritma yang tujuannya bermacam-macam namun men-share tujuannya, sebagai dasar dalam sistem terdistribusi : berupa sekumpulan proses untuk mengkoordinasikan tindakan atau menyetujui satu atau beberapa 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.

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

II. MUTUAL EXCLUSION

Dalam proses distribusi, kita pasti memerlukan kooordinasi dalam aktifitas kita. Sebuah

kumpulan proses yang melakukan share terhadap sumber daya atau sekumpulan sumber daya, membutuhkan mutual exclusion sebagai syarat untuk mencegah interferansi dan memastikan dalam pengaksesan sumber daya. Namun hal ini menimbulkan critical section problem pada domain system operasi yaitu bagaimana melakukan share variable dan fasilitas yang disuplay oleh satu local kernel.

Untuk lebih jelas lagi, misalnya ada seorang user yang ingin melakukan update pada file

text. Untuk memastikan updatean 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 meng-handle locking request dari client.

A. Algoritma untuk Mutal Exclusion Persyaratan yang penting untuk mutual exclusion ada tiga. Pertama, hanya satu proses diizinkan untuk dieksekusi dalam critical section. Kedua, request yang masuk dan keluar dari critical section harus berhasil. Pada syarat yang kedua ini maksudnya, tidak terjadi deadlock dan starvation. Deadlock adalah keadaan dimana ada dua atau lebih proses yang masuk kedalam critical section secara bersamaan. Sedangkan starvation adalah penundaan masuknya sebuah proses yang telah di request. Starvation merupakan sebuah kondisi yang sangat wajar jika terjadi. Wajar jika sebuah proses yang di request tertunda masuk ke critical section, hal ini mungkin disebabkan karena global clocks. Sebelum dilakukan request proses dilakukan penigiriman pesan untuk request masuk ke critical section. Proses ini dapat dilihat pada gambar dibawah ini :

Server mengatur Mutual Exclusion Token

Selanjutnya, kondisi ketiga yaitu pengroderan yang adil dalam masuk ke critical sections.

Sehingga dapat kita evalusi bahwa algoritma untuk mutual exclusion memiliki criteria sebagai berikut :

• Membutuhkan bandwidth untuk proses pengiriman pesan pada tiap kali masuk

dan keluar operasi. • Menimbulkan client delay.

The central server client merupakan cara yang simple agar server bekerja secara adil dalam mengijinkan suatu proses masuk kedalam 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.

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;

III. MULTICAST

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-to-multipoint, dan berbeda dengan cara transmisi unicast.

Sebuah multicast group memiliki sebuah alamat multicast, yaitu kelas D dalam alamat IP versi 4 atau memang alamat multicast dalam alamat IP versi 6. Pada kelas D alamat IP versi 4, alamat yang direservasikan untuk sebuah multicast group adalah 224.0.0.0 hingga 239.255.255.255.

Pada prinsipnya IP Multicasting bekerja dengan cara mengirimkan paket data kepada sekelompok client yang memang membutuhkannya. Dengan cara ini ,data multimedia dikirimkan secara efisien melalui jaringan internet. Semakin banyaknya client tidak akan membebani server, karena server hanya mengirimkan satu paket untuk semua client. Dan client yang tidak membutuhkan paket multicast, tidak akan menerima paket ini , sehingga client tak perlu memproses paket yang tak dibutuhkannya.

A. Algoritma Multicast Routing

Beberapa algoritma telah diusulkan untuk membangun jaringan multicast di mana paket-paket multicast dapat dikirimkan ke titik tujuan. Algoritma ini dapat digunakan dalam penerapan protokol multicast routing.

a. Flooding

Algoritma flooding yang telah telah digunakan pada protokol seperti OSPF adalah teknik yang paling sederhana untuk mengirimkan data multicast ke router pada sebuah jaringan. Pada algoritma ini, ketika router menerima paket multicast maka router pertama-tama akan mengecek apakah paket tersebut pernah sampai ke router atau paket tersebut untuk pertama kalinya sampai ke router. Jika pertama kali, maka router akan meneruskan paket tersebut ke semua interface, kecuali ke interface asal dari paket tersebut. Dengan cara ini maka diyakini semua router akan menerima sedikitnya satu paket.

b. Spanning Trees

Pada algoritma ini, hanya ada satu active path di antara dua router. Ketika router menerima suatu paket multicast, router akan meneruskan paket ke semua jaringan yang merupakan bagian dari spanning tree. Informasi yang harus dijaga oleh router adalah variabel boolean yang menunjukkan apakah jaringan merupakan bagian dari spanning tree atau bukan.

Algoritma Spanning Trees

c. Reverse Path Broadcasting (RPB)

Algoritma RPB sering digunakan pada MBone ( Multicast Backbone). Algoritma ini merupakan modifikasi dari algoritma spanning trees. Pada algoritma ini, ketika router menerima suatu paket multicast pada link \”L\” dan dari sumber \”S\”, router akan memeriksa dan melihat apakah link “L” merupakan jalan terpendek menuju S. Jika iya, paket akan diteruskan pada semua link kecuali L.

d. Truncated Reverse Path Broadcasting (TRPB)

Algoritma TRPB hadir untuk mengatasi kekurangan pada algoritma RPB. Dengan menggunakan protokol IGMP protokol, maka sebuah router dapat menentukan apakah anggota dari kelompok multicast ada pada subnetwork atau tidak ada. Jika subnetwork tidak mempunyai router yang berhubungan dengannya, router akan memotong spanning tree.

e. Steiner Trees (ST)

Pada algoritma RPB dan TRPB, alur terpendek antara titik sumber degan masing-masing titik tujuan digunakan untuk mengirimkan paket multicast. Tetapi algoritma tersebut tidak meminimalkan penggunaan sumber daya jaringan.

Algoritma Steiner Trees

Pada gambar terlihat hanya menggunakan sedikit link. Tipe inilah yang disebut dengan Steiner Trees.

IV. KONSENSUS

– Problem adalah proses untuk menyetujui suatu nilai setelah satu atau lebih proses telah ditaksir berapa seharusnya nilai tersebut.

– Semua komputer mengontrol spaceship yang menentukan untuk menyetujui atau membatalkan.

– Dalam transaksi, komputer yang terlibat harus secara konsisten setuju untuk menampilkan debit dan credit respektif.

– Dalam mutual exclusion, proses setuju dalam setiap proses dapat masuk ke sesi yang kritikal.

– Dalam election, proses setuju dalam setiap proses yang terseleksi.

Model

Proses berkomunikasi dengan message passing.

Mencapai konsesnsus bahkan saat terjadi kesalahan.

Mengasumsikan bahwa komunikasi tersebut terpercaya, tetapi proses dapat saja gagal.

A. The Consensus Problem

Consensus Problem

Persetujuan di dalam nilai dari semua variabel proses yang benar.

Semua proses pi mulai saat undecided state dan mengusulkan satu nilai vi..

Proses berkomunikasi dengan yang lain dengan menukar nilai.

Setiap proses lalu mengeset nilai (di) mereka (value of decision variable) dan memesuki state yang telah ditentukan (decided state) dimana saat itu tidak diperlukan lagi mengubah nilai di.

1

P 2

P3 (crashes)

P1

Consensus algorithm

v 1 =proceed

v 3=abort

v 2=proceed

d1 :=proceed d2 :=proceed

Consensus Problem

Kondisinya harus:

Termination: Secara garis besar, setiap proses yang bemar mengeset decision variabel masing-masing.

Agreement: Decision value dari semua proses yang benar adalah sama jika (pi dan pj) benar dan dapat dimasuki jika decided state (di = dj).

Integrity: Jika proses yang benar semuanya mengusulkan nilai yang sama, maka salah satu proses yang berada di decided state-lah yang menentukan nilainya.

Memecahkan konsensus dalam system dimana proses jangan sampai gagal

Setiap proses harus memulticast nilai yang diusulkannya Setiap proses menunggu sampai semua proses mempunyai nilai N

Lalu mengevaluasi fungsi majority (v1,.., vN), dimana mengembalikan nilai yang sering muncul diantara argumen-argumen, atau tidak mendefinisikan jika tidak ada majority

Termination dijamin kebenarannya dengan operasi multicast Hasil Agreement dan integrity terjamin dengan menilai aspek: definisi dari majority,

dan integritas dari multicast. Jika suatu proses dapat tabrakan, hal ini tidak langsung mengubah algortima yang

sudah ada. Jika suatu proses tiba-tiba gagal maka proses tersebut akan cacat dan dapat

berkomunikasi dengan nilai yang acak.

Ketidakmungkinan di asynchronous systems

Kemungkinan-kemungkinan pendekatan untuk mengatasi hasil yang tidak memungkinkan partially synchronous systems.

1. Masking faults

• Mengatasi setiap roses kesalahan yang ada

• Sebagai contoh: sistem transaksi mempunyai storage dimana mengalami crash

Jika proses crash dan restart maka akan menemukan data-data yang sesuai untuk digunakan kembali secara benar.

Beranggapan bahwa proses benar, tidak ada yang salah, tetapi kadang-kala dapat memakan waktu untuk perform saat proses.

2. Failure detectors

• Proses dapat menyetujui beberapa proses yang tidak merespon.

• Proses yang tidak responsif mungkin tidak benar-benar gagal tetapi yang lain harus berpura-pura seolah hal it sudah selesai teratasi. Hal ini dilakukan dengan cara membuang pesan-pesan yang subsequent dari proses ini.

• Membuat pendeteksi kesalahan seolah-olah akurat dengan melibatkan waktu timeout.

3. Randomization

• Mengenalkan elemen-elemen perubahan dalam proses pengenalan jadi pihak yang jahat (pihak yang menggagalkan proses) tidak dapat mengganggu jalannya proses komunikasi.

• Pihak jahat memanipulasi jaringan untuk menghambat pesan jadi pesan tersebut tiba di waktu yang salah dan karena hal itu pula pesan berada di state yang salah.

B. The Byzantine Generals Problem

Ini adalah proses yang muncul untuk berpartisipasi tetapi tidak mengikuti algoritma yang benar. Ini tidak bermain secara adil. Setiap pertanyaan yang diberikan tidak dijawab dengan benar.Tipe kesalahan ini dinamakan dari masalah komunikasi yang terjadi antara beberapa unit perang Byzantine yang berencana untuk bergabung dan menyerang atau mengalah tergantung hasil observasi dari beberapa musuh. Berikut adalah gambar mengenai Byzantine problem.

Solution with One Faulty Process

• untuk mengatasi masalah Byzantine generals dalam sistem yang sinkron kita membutuhkan N>=3f+1

• untuk f = 1

Babak pertama, komandan mengirimkan nilai ke setiap letnan.

Babak kedua, setiap letnan mengirimkan nilai yang diterimanya ke teman-teman di sebelahnya.

Letnan yang benar hanya perlukan mengapply fungsi simple majority dalam set of values received.

karena N-f-1 >= 2f, fungsi majority akan membuang setiap kesalahan nilai yang ada.

Solution for no commander case

• N general memerlukan update ke setiap komputer dengan nilai mereka. • untuk f < N/3,

Pada babak pertama, setiap general mengirimkan nilainya ke general yang lain.

Pada babak kedua, setiap general mengirimkan nilai vektor yang diterima dari yang lain.

Setelah vektor diterima setiap node akan membandingkan dan memilih nilai majority untuk setiap elemen vektor.

REFERENCE

[1] http://ilmukomputer.com/

[2] George Coulouris. Distributed Systems Consepts and Design.