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
