Distributed Coordinated (Distribusi Terkoordinasi)

EVENT ORDERING (Pengurutan Event)

Pada sistem tersentralisasi :

l  Selalu mungkin menentukan urutan kejadian, sebab hanya terdapat satu memory dan clock

l  Sejumlah aplikasi sangat menekankan urutan, misal : alokasi resource à resource dapat dipakai setelah resource tersebutdipesan dan dijamin bebas.

Pada sistem terdistribusi :

l  Memori & clock  tidak tunggal

l  Tidak mungkin menyatakan urutan dua kejadian

l  Hanya dapatditentukan partial ordering (urutan bagian) à relasi Happened-Before

Relasi Happened Before

Hukum sebab-akibat : suatu pesan dapat diterima setelah pesan tersebutdikirim

Simbol  relasi happened-before : à

1. Jika kejadian A & B berada dlm satu proses  dan A dieksekusi sebelum B, maka ditulis AàB
2. Jika A adalah kejadian pengiriman pesan (sending) oleh sebuah proses dan B adalah sebuah kejadian penerima pesan (receiving) oleh proses lain, maka ditulis A à B
3. Jika A à B dan B à C, maka A à C

Karena suatu event tidak dapat terjadi sebelum dirinya sendiri terjadi, maka relasi happened before tidak bersifat refleksi. 

Jika 2 event A & B tidak memenuhi Relasi à R (A tidak terjadi seblm B & B tidak terjadi sebelum A ), maka kedua event dieksekusi bersamaan (concurent) kedua event tidak dapat saling mempengaruhi. A à B : ada kemungkinan A mempengaruhi B.

Sebagai contoh : sejumlah event direlasikan dgn happened-before.   p1  à q2

                              r0  à  q4

                              q3 à  r1

                              p1 à  q4 ( tentu : p1 à q2 dan q2 à q4)

dan sejumlah event konkuren dari sistem adalah :

                              q0 dan p2

                              r0  dan q3

                              r0  dan p3

                              q3 dan p3

Tidak dapat ditentukan dari 2 event yang konkuren (q0 dan p2) mana yang terjadi dahulu. Namun, karena satu sama lain tidak saling mempengaruhi, maka tidaklah penting untuk mengetahui mana yang dahulu terjadi.

Implementasi

Untuk menentukan event A terjadi sebelum event B diperlukan sebuah clock umum atau suatu  set pensinkron clock yang perfect. Pada sentralisasi ini bisa dilakukan, namun pada terdistribusi kedua hal tersebut tidak mungkin dilakukan.  Sehingga diperlukan definisi khusus dari relasi Happened-before tanpa menggunakan clock physics.  

Maka dikenalkan konsep Timestamp, yaitu   setiap event sistem diasosiasikan dgn timestamp, kemudian didefinisikan global ordering requirement (GOR) untuk setiap pasangan event A & B, jika A à B, maka timestamp A < timestamp B.

• Penerapan GOR dlm lingkungan terdistribusi

Mula-mula didefinisikan dlm tiap proses Pi suatu logical clock (LCi). LCi dapat diimplementasikan sebagai  counter sederhana  yang di-increment-kan antara 2 event tereksekusi berurutan dlm suatu proses. Dimana LCi tersebut dapat menunjukan nomer event secara unik, sehingga jika event terjadi sebelumevent B dalam proses Pi, maka LCi (A) <  LCi (B).

•  Clock Lojik

Dapat diimplementasikan sbg counter yang diinkremen setiap eksekusi event berurutan pada satu proses

– Tiap proses Pi memiliki clock lojik LCi

– Pada proses Pi , jika A terjadi sebelum B maka LCi (A) < LCi (B)

– Antar proses, jika proses Pi menerima pesan (event B) dgn timestamp t sedangkan LCi (B) < t, maka Pi harus memajukan clocknya sehingga LCi (B) = t + 1

 MUTUAL EXCLUSION

• CENTRALIZED APPROACH

Dalam CA untuk menentukan mutual exclusion, salah satu proses akan dipilih untuk mengkoordinasikan masuk ke critical section.

Algoritma ini pasti menjamin mutual exclusion. Policy (kebijaksanaan secheduling oleh koordinator bersifat fair ), tidak terjadi starvation dan hanya memerlukan 3 pesan untuk setiap memasuki c.s : request, reply, release

• FULLY DISTRIBUTED APPROACH

Pendistribusian Decision – Making ke seluruhan sistem sukar & kompleks. Dikenalkan algoritma berbasis “Event Ordering “, sebagai berikut:

l  Ketika suatu proses Pi ingin masuk ke critical section,  maka ia akan  meng-create timestamp    baru (Ts) dan mengirim pesan request    (Pi,Ts) ke semua proses lain dlm sistem    (termasuk dirinya sendiri)

l     Pada penerimaan pesan request, sebuah proses dapat:

-       segera menjawab kembali ke Pi

-       menunda jawaban (karena masih berada di dlm c.s)

l Proses yang telah menerima pesan jawaban dari semua proses lain dlm sistem dapatmemasuki c.s mengantrikan request yang datang dan menahan mereka.

l  Setelah keluar dari c.s, proses mengirim pesan jawaban kepada semua proses yang requestnya ditahan

l  Keputusan suatu proses Pi menjawab langsung atau menahan dahulu request (Pj,Ts) didasarkan pada 3 faktor :
Jika proses Pi berada dalam critical section, maka ia akan menahan jawaban ke PjJika proses Pi tidak dalam c.s, maka ia akan segera menjawab ke PjJika proses Pi ingin masuk ke c.s, tetapi blm dapatmasuk, maka ia akan membandingkan timestamp request miliknya dgn timestamp request yang datang dari Pj.

Algoritma ini dapat berhasil dengan syarat

l  Mutual exclusion dapat ditentukan

l  Dijamin bebas dead-lock

l  Dijamin bebas starvation (masuk c.s dijadwalkan berdasarkan urutan timestamp, dimana urutan timestamp menjamin FIFO)

l  Jumlah pesan per critical section entry = 2x (n-1).

Suatu jumlah minimum yang diperoleh per c.s entry, bila proses-proses bekerja independen dan konkuren

Skenario ini memerlukan partisipasi dari semua proses dlm sistem. Pendekatan ini memp 2 konsekuensi :

1.   Proses perlu tahu identitas semua proses lain dlm sistem. Jika ada proses baru bergabung dgn group proses yang berpartisipasi dlm alg mutual excl, maka perlu langkah :

a.  Proses harus menerima semua nama proses lain dlm group

b.  Nama proses baru harus di distribusikan ke semua proses lain dlm group

2.    Jika salah satu proses fail, skema keseluruhan collaps

3.  Dapat diatasi dgn memonitor scr kontinyu status semua proses dlm sistem jika sebuah proses fail, maka semua proses yang lain diberitahu agar tidak mengirim pesan ke proses yang fail tersebut

4. Jika proses direcover, ia hrs menginisialisasikan procedure yang mengizinkan untuk bergabung dgn group tersebut.

•  TOKEN PARSING APPROACH

Token merupakan pesan bertipe khusus yang beredar pada seluruh sistem. Dengan menggerakkan token diantara proses-proses dalam suatu sistem dapat menentukan mutual exclusion. Hanya  ada satu token dalam sistem sehingga hanya ada satu proses yang dapatmasuk ke c.s pada suatu saat.

Proses-proses diorganisasikan secar logika dalam bentuk Ring (fisiknya jaringan tidak perlu Ring). Selama proses-proses  saling berhubungan,sangat mungkin di implementasikan suatu Logical-Ring

Dua jenis kesalahan yang mungkin terjadi :

l   Token hilang :  memanggil “ election” untuk membangkitkan Token baru.

l   Proses fail : struktur Ring baru harus dibentuk.

ATOMISCITY (ATOMISITAS)

Tiap situs memiliki koordinator transaksi yg berfungsi menjamin atomisitas eksekusi transaksi, dengan cara:

-       memulai eksekusi transaksi

-       memecah menjadi beberapa sub-transaksi dan mendistribusikannya pada situs-situs yg cocok utk dieksekusi

-       mengkoordinasikan terminasi transaksi (commit, atau abort)

Asumsikan bahwa tiap situs menyimpan log untuk tujuan recovery

• Protokol Two-Phase Commit (2PC)

Semua situs yg mengeksekusi transaksi T harus memiliki hasil akhir yg sama (commit atau abort). JikaT adalah transaksi yg diinisiasi pada situs Si dengan koordinator Ci , maka setelah transaksi selesai Ci memulai protokol 2PC:

-       Fase1: Ci mengirimkan pesan ke semua situs yg mengeksekusi T untuk mengetahui transaksi commit atau abort

-    Fase2: Ci menentukan hasil akhir transaksi setelah menerima respon dari semua situs; transaksi commit jika semua situs memberi respon commit

• Penanganan Kegagalan pada 2PC

Kegagalan dapat terjadi pada salah satu situs yg berpartisipasi, sehingga masalah yang muncul adalah situs yang selesai melakukan recovery harus memeriksa log untuk menentukan status transaksi

– Jika commit, situs melakukan redo(T)

– Jika abort, situs melakukan undo(T)

Kegagalan pada Situs yang Berpartisipasi

Jika log berisi <commit T>, maka situs akan melakukan redo(T)

Jika log berisi <abort T>, maka situs akan melakukan undo(T)

Jika log berisi <ready T> maka akan consult Ci

Kegagalan pada coordinator

Maka masalahnya adalah situs yg berpartisipasi harus menentukan nasib T

Jika salah satu situs berisi record <commitT> atau <abortT>, maka coordinator akan mengikuti hasilnya.

 Jika ada situs yg belum berisi <ready T> maka koordinator tdk dpt memutuskan.

Kegagalan pada jaringan

– Masalah: pesan yg dikirimkan tidak sampai

– Jika beberapa link terputus dapat dilakukan partisi jaringan

CONCURRENCY CONTROL

Manajer transaksi berfungsi :

-       mengelola eksekusi transaksi yg mengakses data

-       Menyimpan log untuk tujuan recovery

-  Berpartisipasi dalam skema kontrol-konkurensi untuk mengkoordinasi eksekusi transaksi

• Protokol Locking

Skema nonreplikasi

-       Tiap situs memiliki satu manajer lock lokal untuk mengelola permintaan lock/unlock data yg disimpan pada situs tsb

-       Keuntungan: sederhana

-       Kerugian: penanganan deadlock lebih rumit karena tdk ditangani oleh satu situs

Pendekatan Koordinator Tunggal

-       Ada manajer lock tunggal yg berada pada salah satu situs utk menangani permintaan lock/unlock data

-       Read dpt dilakukan pada situs mana saja yg menyimpan data

-       Write dilakukan pada semua replikasi

• Protokol Mayoritas

Tiap situs memiliki lock manajer yg mengelola data dan duplikat data yg disimpan pd situs tsb. – Untuk melakukan lock thd data Q yg direplikasi pd beberapa situs, transaksi mengirim request lock ke > ½ situs yg menyimpan Q. Lock manajer menentukan lock yg dapat diberikan. Transaksi terhadap data tdk dimulai sebelum kunci dari mayoritas replika diperoleh

Keuntungan: penanganan terdesentralisasi

Kerugian: penanganan deadlock perlu modifikasi, rumit

• Protokol Bias

Protokol bias mirip dengan protokol mayoritas. Perbedaannya adalah bahwa

permintaan shared lock diberikan perhatian lebih daripada permintaan exclusive lock.

Keuntungan: lebih baik daripada protocol bias

Kerugian: penanganan deadlock lebih rumit

DEADLOCK HANDLING

Deadlock Prevention and Handling

• Pencegahan Deadlock: Menjamin bahwa tidak pernah terjadi kebuntuan
• Periksa transaksi ketika dimulai, dan mulai hanya jika semua sumber daya yang dibutuhkan tersedia.
• Semua sumber daya yang mungkin dibutuhkan oleh transaksi harus predeclared

• Menghindari Deadlock: Mendeteksi kebuntuan potensial di muka dan mengambil tindakan untuk memastikan bahwa kebuntuan tidak akan terjadi. Transaksi yang diizinkan untuk melanjutkan kecuali sumber daya yang diminta tidak tersedia
• Dua pendekatan yang berbeda:

• Prioritaskan transaksi: Mengatasi kebuntuan dengan membatalkan transaksi dengan lebih tinggi atau prioritas yang lebih rendah. Skema berikut menganggap bahwa permintaan Ti memegang kunci dengan Tj:
• Wait Die Scheme: jika ts (Ti) <TS (Tj) maka Ti menunggu, jika tidak Ti yang lain die
• Wound-Wait Secheme: jika ts (Ti) <TS (Tj) maka Tj wounds (dibatalkan), jika tidak maka Ti menunggu

 Deadlock Detection

 Transaksi yang diizinkan untuk menunggu bebas, dan karenanya bisa mengakibatkan kebuntuan. Periksa Global-WFG apakah ada siklus. Jika kebuntuan ditemukan, hal ini diselesaikan dengan membatalkan salah satu transaksi yang terlibat (juga disebut korban).

ELECTION ALGORITHM (ALGORITMA PEMILIHAN)

Banyak algoritma tersebar membutuhkan sebuah proses yang berfungsi sebagai koordinator, inisiator, sekuenser, atau pelaksana fungsi khusus lain. Beberapa contoh seperti koorinator pada algoritma mutual exclusion terpusat.

Bila koordinator mengalami kegagalan karena hostnya down, sistem harus dapat melanjutkan eksekusi hanya dengan memulai lagi sebuah copy proses koordinator baru di host lain. Algoritma yang menentukan dimana hal tersebut harus dimulai dinamakan algoritma pemilihan.

• Bully Algorithm
• Ring Algorithm