Time And Coordination

Time And Coordination

·         Time And Coordination

adalah mengkordinasikan waktu dalam transfer data,  agar tidak terjadi ketimpangan pada proses transfer data.  Selain itu juga, berguna untuk mengukur penundaan antara komponen terdistribusi, menyinkronkan aliran data misalnya: suara dan video,  dan sebagai penanda keakuratan waktu untuk mengidentifikasi atau  mengotentikasi transaksi bisnis dan serializability dalam database terdistribusi dan keamanan protocol.

·         Apa itu waktu?

Bagaimana  Anda mengkoordinasikan didistribusikan komputer jika tidak ada waktu global. Tidak ada Waktu global bahwa setiap orang dapat melakukan sinkronisasi. Sinkronisasi dapat di lakukan apabila Dua sistem setuju untuk apa waktu itu dan dengan menggunakan clock eksternal dan jam lokal (subset eksternal). Salah satu pendekatan untuk sinkronisasi dua sistem: Kirim pesan dengan waktu, t, receiver menetapkan waktu untuk t + waktu transmisi

·         NTP - Network Time Protocol

Dirancang untuk: Sinkronisasi komputer pada jaringan besar dengan UTC. Keandalannya  Bisa bertahan kerugian panjang dengan konektivitas Memberikan melayang secara signifikan kurang dari jam motherboard. Keamanan terhadap penolakan layanan dan spoofing

Pengurutan Event

• Pengurutan event sangat diperlukan, al. untuk alokasi resources

• Pada DS tidak ada memori dan clock milik bersama 􀃆 pengurutan event bersifat relatif terhadap waktu (relasi happened before)

Relasi Happened Before

• Aturan:

– Jika A dan B adalah event pada proses yg sama, dan A dieksekusi sebelum B, maka A 􀃆 B

– Jika A adalah event pengiriman pesan oleh satu proses dan B adalah event penerimaan pesan oleh proses lain, maka A 􀃆 B

– Jika A 􀃆 B dan B 􀃆 C, maka A 􀃆 C

– Relasi 􀃆 bersifat irreleflexive partial ordering

– Jika A 􀃆 B, mungkin A dan B saling mempengaruhi

– Jika event A dan B tidak terkait dgn relasi , maka 􀃆A dan B konkuren (saling tidak mempengaruhi)

Implementasi

• Idealnya, diperlukan satu clock milik bersama atau kumpulan clock yg disinkronisasikan

• Global ordering menggunakan timestamp:

– untuk tiap pasang A dan B, jika A 􀃆 B maka timestamp A < timestamp B

• Clock Lojik, dapat diimplementasikan sbg counter yg 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

Pendekatan Tersentralisasi (Centralized)

• Salah satu proses dipilih sebagai koordinator utk mengatur entri ke CS

• Menggunakan pesan request-reply-release untuk masuk ke CS

• (+): menjamin mutex, dpt menjamin fairness (no starvation)

• (--): jika koordinator gagal 􀃆 perlu dipilih kembali

Pendekatan Terdistribusi Penuh (Fully Distributed)

• Untuk masuk ke CS, proses mengirimkan pesan request (Pi, TS) ke semua proses

• Pengiriman reply oleh Pi ke Pk :

– Jika Pi sedang berada di CS, reply ke Pk ditunda

– Jika Pi tidak akan masuk ke CS, reply langsung dikirim ke Pk

– Jika Pi akan masuk ke CS dan TS(Pi) < TS(Pk) maka reply ke Pk ditunda

• (+): menjamin mutex, bebas deadlock dan starvation

• (--): jumlah pesan minimum 2(n-1), proses harus tahu identitas semua proses lain, tidak berfungsi jika ada proses yg gagal, mengganggu proses lain yg tidak akan masuk ke CS

Pendekatan Token Passing

• Menggunakan satu token yg beredar diantara proses

• Hanya proses yg memiliki token saat itu yg dapat masuk ke CS

• Syarat: adanya lingkaran lojik yg menghubungkan semua proses

• (+): menjamin mutex, bebas starvation

• (--): jika token gagal 􀃆 perlu digenerate kembali, jika proses gagal 􀃆 perlu dibentuk ring lojik baru