LOGICAL CLOCK AND SYNCHRONIZATION

KELOMPOK 5 TIME AND COORDINATION

NPM NAMA

10107005 ABDUL AZIZ

10107146 ALIF ANANDITO

12107054 ANDRI IRAWAN ISA PUTRA

10107203 ANGGI PURNAMA

10107765 HABIBI SEGAP AL HAMID

Universitas gunadarma

Logical clock and synchronization

Waktu adalah hal yang penting dalam sistem terdistribusi karena beberapa hal Pertama

waktu adalah satuan akurasi Untuk mengetahui kapan suatu peristiwa terjadi dibutuhkan

sinkronisasi clock pada sistem dan di luar sistem Sebagai contoh transaksi e-commerce terjadi

di komputer pengguna dan komputer bank Kejadian tersebut haruslah dicatat waktunya secara

akurat untuk keperluan audit Kedua algoritma mengenai sinkronisasi clock memiliki beberapa

masalah antara lain mempertahankan konsistensi data yang didistribusikan otentikasi request

yang dikirim ke server dan menghapus proses yang terduplikasi

Jika dianalogikan seperti teori relativitas milik Einstein Suatu kejadian yang diamati

oleh pengamat yang satu bisa saja berbeda dengan pengamat lainnya dalam hal interval (jeda)

waktu Dalam sistem terdistribusi masalahnya adalah mencatat waktu terjadinya suatu kejadian

pada node yang berbeda-beda secara akurat sehingga dapat diketahui mana yang hanya terjadi

dan mana yang terjadi secara serempak

1 Clock Kejadian dan Process State

11 Clock (Jam)

Setiap komputer pasti memiliki clock fisik Clock adalah alat elektronik yang menghitung

osilasi yang terjadi pada kristal pada frekuensi tertentu dan menyimpannya dalam counter

register Sistem operasi membaca clock fisik tersebut dan menerjemahkannya ke software clock

Software clock tidak selalu akurat sehingga pewaktuan hardware dan software memiliki

perbedaan walaupun sangat kecil Namun software clock tetap menjadi acuan pencatatan waktu

setiap kejadian proses Kejadian yang terjadi setelah suatu kejadian akan tercatat di waktu yang

berbeda apabila resolusi clock (periode update software clock) lebih kecil daripada interval

waktu antar kejadian

12 Clock Skew And Clock Drift

Clock milik tiap-tiap komputer tidak selalu sama Perbedaan antara pembacaan dua clock

komputer berbeda disebut skew Sedangkan perbedaan clock rate disebut clock drift Pada clock

fisik osilasi frekuensi dan temperatur mempengaruhi perbedaan clock tiap komputer

Perbedaannya mungkin sangat kecil tetapi akumulasi perbedaan tersebut dapat mencapai tahap

yang bisa diamati dengan mata telanjang walaupun sudah disamakan nilainya Clock drift rate

adalah perubahan perbedaan pembacaan antara clock dan perfect reference clock (clock yang

dijadikan acuan)

13 Waktu Universal Terkoordinasi (Coordinated Universal Time)

Clock komputer dapat disinkronkan dengan clock luar yang akurasinya tinggi Clock

yang akurasinya paling tinggi menggunakan osilator atom Keluaran clock ini digunakan sebagai

standar waktu international Coordinated Universal Time (UTC) adalah standar internasional

untuk penjagaan waktu (timekeeping) Sinyal UTC disiarkan dari stasiun radio dan satelit ke

seluruh dunia Komputer dengan penerima sinyal di seluruh dunia dapat mensinkronkan

clocknya dengan sinyal ini

2 Sinkronasi Clock Fisik

Untuk mengetahui kapan sebuah peristiwa terjadi secara akurat pada proses system

terdistribusi diperlukan sinkronisasi dengan sumber waktu dari luar yang disebut sinkronisasi

eksternal (external synchronization) Dan jika satu clock tersinkronisasi dengan clock yang lain

dengan derajat akurasi yang diketahui maka kita bisa mengukur interval terjadinya dua peristiwa

pada komputer yang berbeda walaupun tidak tersinkronisasi ke sumber waktu dari luar Hal ini

disebut sinkronisasi internal (internal synchronization)

Beberapa gagasan pengkoreksian (correctness) untuk clock sudah pernah diajukan

Hardware clock H selalu dikoreksi apabila drift-nya sudah mencapai angka tertentu (ρ gt 0) Jadi

galat (error) perhitungan interval antara waktu sebenarnya t dan trsquo (t gt trsquo) adalah

(1 - ρ)(t - t) le H(t) - H(t) le (1 + ρ)(t -t)

Clock yang tidak menerima pengkoreksian apapun dinyatakan faulty Clock dinyatakan crash

failure ketika berhenti berdetik sama sekali Kegagalan clock lainnya adalah arbitrary failure

Contoh arbitrary failure adalah lsquoY2K bugrsquo yang terjadi pada pergantian tahun 1999 ke 2000

Setelah 31 Desember 1999 dilanjutkan ke 1 Januari 1900 Catatan clock tidak harus akurat

untuk menjadi benar

21 Sinkronisasi pada Sistem Sinkron

Pada sistem sinkron sebuah proses mengirim waktu t dari clock lokalnya ke proses

lainnya dalam pesan m Proses seharusnya menerima dan mencocokkannya dengan clock

lokalnya sendiri dengan t + Ttrans di mana Ttrans adalah waktu transmisi Sayangnya Ttrans

bervariasi dan sulit diketahui Namun waktu minimal transmisi min tetap dapat diperkirakan

apabila jaringan lancar dan tidak ada proses lain yang berjalan bersamaan Sistem terdistribusi

yang banyak digunakan adalah asinkron Delay pesan tidak terbatas atau tergantung masing-

masing clock komputer Pada sistem asinkron Ttrans = min + x di mana x ge 0 Nilai x tidak

diketahui tetapi dapat diukur

22 Metode Cristian untuk Sinkronisasi Clock

Cristian menyarankan untuk menggunakan server yang menerima sinyal UTC untuk

mensiknronisasikan komputer secara eksternal Sebuah proses p meminta waktu dalam pesan m

kepada server S kemudian menerima nilai waktu t dalam pesan mt Proses p merekam total

waktu yang dibutuhkan Tround untuk mengirim permintaan dan menerima balasan Dengan

begini waktu yang akurat dapat diperhitungkan Permasalahannya adalah server yang

menyimpan waktu hanya satu yang apabila gagal maka untuk sementara waktu sinkronisasi

tidak dapat dilakukan Cristian menyarankan untuk menggunakan beberapa server yang sudah

tersinkronasi Jadi klien meminta ke semua server dan hanya menggunakan balasan yang

pertama kali diterima

23 Algoritma Berkeley

Gusella dan Zatti mengembangkan algoritma untuk sinkronisasi internal Mereka

mengembangkan algoritma ini pada komputer berbasis Barkeley UNIX Pada lagoritma ini

sebuah komputer ditunjuk sebagai coordinator yang disebut master Komputer ini kemudian

memilih komputer-komputer untuk dimintai sinkronisasi yang disebut slave dengan master

secara periodik Slave-slave membalas dengan nilai clock miliknya Master menghitung

clocknya sendiri dengan memperhitungkan waktu perjalanan data dan rata-rata dari nilai clock

yang didapat Algoritma ini tidak akan membaca clock yang faulty Clock yang hanya berbeda

sedikit dengan jumlah tertentu dengan clock lainnya yang dipilih untuk dirata-rata Hal ini

disebut fault tolerant average Sehingga ketika ada satu clock yang gagal atau rusak tidak

mempengaruhi clock Master

24 Protokol Waktu Jaringan (Network Time Protocol)

Metode Cristian dan algoritma Berkeley pada dasarnya digunakan untuk komunikasi

intranet Protokol Waktu Jaringan (NTP) mendefinisikan arsitektur untuk pelayanan waktu dan

protocol untuk distribusi informasi waktu lewat internet Tujuan dan fitur NTP antara lain

Untuk menyediakan layanan yang memungkinkan klien di Internet yang akan disinkronkan akurat

UTC

Untuk menyediakan layanan yang bisa bertahan di jaringan mengalami loss karena jarak

Untuk mengaktifkan klien untuk mensinkronisasi cukup sering untuk mengimbangi tingkat drift

ditemukan di kebanyakan komputer NTP

Untuk menyediakan perlindungan terhadap interferensi dari layanan waktu baik galat

maupun ketidaksengajaan

Layanan NTP tersebar pada banyak server di internet Server utama tersambung langsung

ke sumber waktu seperti penerima sinyal radio UTC Server sekunder disinkronisasi dengan

server primer Server-servernya tersambung dalam hierarkikal logika yang disebut

synchronization subnet seperti Gambar 3 Semakin keatas levelnya akan semakin akurat clock-

nya Galat terjadi setiap melewati satu level Server-server NTP bersinkronasi satu sama lain

dengan tiga cara antara lain multicast procedure-call dan symmetric

1 Multicast ditujukan untuk LAN berkecepatan tinggi Satu atau lebih server secara periodik

menyebar waktu clock ke server di komputer lain yang tersambung di LAN Mode ini akurasinya

rendah tetapi cocok untuk berbagai kepentingan

2 Procedure-call hampir sama dengan algoritma Cristian Server menerima request dari

komputer lain dan membalasnya dengan pembacaan clock saat pengiriman Mode ini cocok

ketika keakurasian tinggi dibutuhkan atau ketika multicast tidak dappat dilakukan

3 Mode symmetric ditujukan untuk server yang mensuplai waktu dalam LAN atau pada level

tertinggi dari sebuah synchronization subnet

Pada mode procedure-call dan symmetric mode memroses pertukaran bagian-bagian

pesan Tiap pesan memiliki catatan waktu dari peristiwa yang baru saja terjadi yaitu waktu local

ketika pesan tersebut dikirimkan Seperti pada Gambar 4 pesan m menyimpan catatan waktu

setiap akan ditransmisikan yaitu Ti-3 dan Ti-1 dan ketika diterima yaitu Ti-2 dan Ti

Kemudian NTP menghitung jeda waktu antara dua clock komputer

3 Logical Time and Logical Clock

Dari sudut pandang dari setiap single proses event-event diurutkan berdasakan waktu

seperti pada local clock Tetapi seperti yang dikatakan oleh Lamport [1978] kita tidak dapat

melakukan singkronisasi clock secara sempurna pada sebuah sistem terdistribusi Kita tidak

dapat secara umum menggunakan physical time untuk menentukan urutan dari suatu event yang

terjadi Secara umum kita dapat menggunakan sebuah skema yang mirip dengan physical tapi

pada sistem terdistribusi digunakan untuk mengurutkan event-event yang terjadi pada proses

yang berbeda Pengurutan ini berdasarkan pada dua hal yang simple dan intuitif

Jika dua event terjadi bersamaam pada satu process yang sama pi (i = 12 hellip N) kemudian

event-event tersebut terjadi sesuai dengan urutan pi yang kita sebutkan diatas

Kapan saja sebuah message dikirim diantara proses-proses event dari pengiriman message

terjadi sebelum event dari penerimaan message

Lamport menyebutkan partial ordering diperoleh dengan men-generalalisasikan kedua hubungan

ini relasi happened-before Istilah ini biasa juga disebut causal ordering atau potential causal

ordering Kita dapat mendefinisikan relasi happened-before dinotasikan dengan 1048890 seperti

berikut

HB1 Jika ᴲ process pi e iersquo maka e ersquo

HB2 untuk setiap message m send(m) receive(m)

- Dimana send(m) adalah event dari pengiriman message dan receive(m) adalah event dari

penerimaan message

HB3 Jika e ersquo dan erdquo adalah event dimana e ersquo dan ersquo erdquo maka e erdquo

Relasi diilustrasikan pada gambar 5 Pada ketiga proses tersebut dapat dikombinasikan

menjadi a f Antar a dan e tidak ada relasi maka ditulis a e

31 Logical Clocks

Lamport menemukan sebuah mekanisme yang simple untuk mengurutkan happened-

before secara numeris Mekanisme ini disebut logical clock Lamport logical clock adalah

software counter yang bertambah secara monoton dimana nilainya tidak perlu menanggung

hubungan tertentu ke suatu physical clock Setiap proses pi tetap berada pada logical clock

masing-masing Timestamp dari suatu event e pada pi disini dinotasikan dengan Li(e) dan L(e)

Untuk notasi dalam suatu prose adalah sebagai berikut

LC 1 Li bertambah sebelum setiap event muncul pada proses pi Li = Li + 1

LC 2 (a) Ketika sebuah proses pi mengirim sebuah message m nilai L juga ditempelkan pada

nilai m t = Li

(b) pada saat menerima pesan (mt) sebuah proses pj menghitung L j = max(Lj t) dan lalu

mengaplikasikan LC1 sebelum melakukan timestamp untuk event receive(m)

32 Totally ordered logical clocks

Beberapa pasang event yang berbeda yang dihasilkan oleh proses yang berbeda telah

diidentifikasi dengan Lamport timestamp secara numeris Namun kita dapat menciptakan sebuah

urutan total peristiwa yaitu satu untuk yang semua pasangan dari event yang berbeda terjadi

Jika e adalah sebuah peristiwa yang terjadi di pi dengan local timestamp Ti dan e adalah sebuah

event yang terjadi di pj dengan local timestamp Tj kita mendefinisikan global logic timestamp

untuk event ini menjadi (Ti i) dan (Tj j) Dan kita define (Ti i) lt(Tj j) jika hanya jika salah Ti

ltTj atau Ti = Tj dan i ltj terpenuhi Urutan ini tidak memiliki arti fisik umum (karena

pengidentifikasi proses yang tidak beraturan) tetapi kadang-kadang berguna Lamport

menggunakannya misalnya untuk mengurutkan proses masuknya ke bagian kritis

33 Vector clocks

Mattern [1989] dan Fidge [1991] mengembangkan vector clocks untuk mengatasi

kekurangan pada Lamport clocks fakta bahwa dari L(e) lt L(ersquo) kita tidak dapat menyimpulkan

bahwa e ersquo Vektor clock untuk sebuah sistem dari N proses adalah sebuah array dari N

integer Setiap proses berada pada vektor clock Vi masing-masing Aturan adalah sebagai berikut

VC1 Inisialisasi Vi [j] = 0 for ij = 12hellip N

VC2 sesaat sebelum pi men-timestamp sebuah event diset Vi[i] = Vi[i] + 1

VC3 pi memasukan nilai t = Vi pada setiap message yang diirim

VC4 Ketika pi menarima sebuah timestamp t pada sebuah sebuah message pi di set Vi[j] =

max(Vi[j] t[j]) for j = 12hellipN

DAFTAR PUSTAKA

Herusetyo Arif Time and Global State UGM Publisher Yogyakarta

2006

L Lamport Time Clocks And The Ordering Of Events In A Distributed

System Computer Science Laboratory SRI International Massachusett

1990

Coulouris George Distributed System Concept and Design Addison

Press Wesley 2001

Logical clock and synchronization

Waktu adalah hal yang penting dalam sistem terdistribusi karena beberapa hal Pertama

waktu adalah satuan akurasi Untuk mengetahui kapan suatu peristiwa terjadi dibutuhkan

sinkronisasi clock pada sistem dan di luar sistem Sebagai contoh transaksi e-commerce terjadi

di komputer pengguna dan komputer bank Kejadian tersebut haruslah dicatat waktunya secara

akurat untuk keperluan audit Kedua algoritma mengenai sinkronisasi clock memiliki beberapa

masalah antara lain mempertahankan konsistensi data yang didistribusikan otentikasi request

yang dikirim ke server dan menghapus proses yang terduplikasi

Jika dianalogikan seperti teori relativitas milik Einstein Suatu kejadian yang diamati

oleh pengamat yang satu bisa saja berbeda dengan pengamat lainnya dalam hal interval (jeda)

waktu Dalam sistem terdistribusi masalahnya adalah mencatat waktu terjadinya suatu kejadian

pada node yang berbeda-beda secara akurat sehingga dapat diketahui mana yang hanya terjadi

dan mana yang terjadi secara serempak

1 Clock Kejadian dan Process State

11 Clock (Jam)

Setiap komputer pasti memiliki clock fisik Clock adalah alat elektronik yang menghitung

osilasi yang terjadi pada kristal pada frekuensi tertentu dan menyimpannya dalam counter

register Sistem operasi membaca clock fisik tersebut dan menerjemahkannya ke software clock

Software clock tidak selalu akurat sehingga pewaktuan hardware dan software memiliki

perbedaan walaupun sangat kecil Namun software clock tetap menjadi acuan pencatatan waktu

setiap kejadian proses Kejadian yang terjadi setelah suatu kejadian akan tercatat di waktu yang

berbeda apabila resolusi clock (periode update software clock) lebih kecil daripada interval

waktu antar kejadian

12 Clock Skew And Clock Drift

Clock milik tiap-tiap komputer tidak selalu sama Perbedaan antara pembacaan dua clock

komputer berbeda disebut skew Sedangkan perbedaan clock rate disebut clock drift Pada clock

fisik osilasi frekuensi dan temperatur mempengaruhi perbedaan clock tiap komputer

Perbedaannya mungkin sangat kecil tetapi akumulasi perbedaan tersebut dapat mencapai tahap

yang bisa diamati dengan mata telanjang walaupun sudah disamakan nilainya Clock drift rate

adalah perubahan perbedaan pembacaan antara clock dan perfect reference clock (clock yang

dijadikan acuan)

13 Waktu Universal Terkoordinasi (Coordinated Universal Time)

Clock komputer dapat disinkronkan dengan clock luar yang akurasinya tinggi Clock

yang akurasinya paling tinggi menggunakan osilator atom Keluaran clock ini digunakan sebagai

standar waktu international Coordinated Universal Time (UTC) adalah standar internasional

untuk penjagaan waktu (timekeeping) Sinyal UTC disiarkan dari stasiun radio dan satelit ke

seluruh dunia Komputer dengan penerima sinyal di seluruh dunia dapat mensinkronkan

clocknya dengan sinyal ini

2 Sinkronasi Clock Fisik

Untuk mengetahui kapan sebuah peristiwa terjadi secara akurat pada proses system

terdistribusi diperlukan sinkronisasi dengan sumber waktu dari luar yang disebut sinkronisasi

eksternal (external synchronization) Dan jika satu clock tersinkronisasi dengan clock yang lain

dengan derajat akurasi yang diketahui maka kita bisa mengukur interval terjadinya dua peristiwa

pada komputer yang berbeda walaupun tidak tersinkronisasi ke sumber waktu dari luar Hal ini

disebut sinkronisasi internal (internal synchronization)

Beberapa gagasan pengkoreksian (correctness) untuk clock sudah pernah diajukan

Hardware clock H selalu dikoreksi apabila drift-nya sudah mencapai angka tertentu (ρ gt 0) Jadi

galat (error) perhitungan interval antara waktu sebenarnya t dan trsquo (t gt trsquo) adalah

(1 - ρ)(t - t) le H(t) - H(t) le (1 + ρ)(t -t)

Clock yang tidak menerima pengkoreksian apapun dinyatakan faulty Clock dinyatakan crash

failure ketika berhenti berdetik sama sekali Kegagalan clock lainnya adalah arbitrary failure

Contoh arbitrary failure adalah lsquoY2K bugrsquo yang terjadi pada pergantian tahun 1999 ke 2000

Setelah 31 Desember 1999 dilanjutkan ke 1 Januari 1900 Catatan clock tidak harus akurat

untuk menjadi benar

21 Sinkronisasi pada Sistem Sinkron

Pada sistem sinkron sebuah proses mengirim waktu t dari clock lokalnya ke proses

lainnya dalam pesan m Proses seharusnya menerima dan mencocokkannya dengan clock

lokalnya sendiri dengan t + Ttrans di mana Ttrans adalah waktu transmisi Sayangnya Ttrans

bervariasi dan sulit diketahui Namun waktu minimal transmisi min tetap dapat diperkirakan

apabila jaringan lancar dan tidak ada proses lain yang berjalan bersamaan Sistem terdistribusi

yang banyak digunakan adalah asinkron Delay pesan tidak terbatas atau tergantung masing-

masing clock komputer Pada sistem asinkron Ttrans = min + x di mana x ge 0 Nilai x tidak

diketahui tetapi dapat diukur

22 Metode Cristian untuk Sinkronisasi Clock

Cristian menyarankan untuk menggunakan server yang menerima sinyal UTC untuk

mensiknronisasikan komputer secara eksternal Sebuah proses p meminta waktu dalam pesan m

kepada server S kemudian menerima nilai waktu t dalam pesan mt Proses p merekam total

waktu yang dibutuhkan Tround untuk mengirim permintaan dan menerima balasan Dengan

begini waktu yang akurat dapat diperhitungkan Permasalahannya adalah server yang

menyimpan waktu hanya satu yang apabila gagal maka untuk sementara waktu sinkronisasi

tidak dapat dilakukan Cristian menyarankan untuk menggunakan beberapa server yang sudah

tersinkronasi Jadi klien meminta ke semua server dan hanya menggunakan balasan yang

pertama kali diterima

23 Algoritma Berkeley

Gusella dan Zatti mengembangkan algoritma untuk sinkronisasi internal Mereka

mengembangkan algoritma ini pada komputer berbasis Barkeley UNIX Pada lagoritma ini

sebuah komputer ditunjuk sebagai coordinator yang disebut master Komputer ini kemudian

memilih komputer-komputer untuk dimintai sinkronisasi yang disebut slave dengan master

secara periodik Slave-slave membalas dengan nilai clock miliknya Master menghitung

clocknya sendiri dengan memperhitungkan waktu perjalanan data dan rata-rata dari nilai clock

yang didapat Algoritma ini tidak akan membaca clock yang faulty Clock yang hanya berbeda

sedikit dengan jumlah tertentu dengan clock lainnya yang dipilih untuk dirata-rata Hal ini

disebut fault tolerant average Sehingga ketika ada satu clock yang gagal atau rusak tidak

mempengaruhi clock Master

24 Protokol Waktu Jaringan (Network Time Protocol)

Metode Cristian dan algoritma Berkeley pada dasarnya digunakan untuk komunikasi

intranet Protokol Waktu Jaringan (NTP) mendefinisikan arsitektur untuk pelayanan waktu dan

protocol untuk distribusi informasi waktu lewat internet Tujuan dan fitur NTP antara lain

Untuk menyediakan layanan yang memungkinkan klien di Internet yang akan disinkronkan akurat

UTC

Untuk menyediakan layanan yang bisa bertahan di jaringan mengalami loss karena jarak

Untuk mengaktifkan klien untuk mensinkronisasi cukup sering untuk mengimbangi tingkat drift

ditemukan di kebanyakan komputer NTP

Untuk menyediakan perlindungan terhadap interferensi dari layanan waktu baik galat

maupun ketidaksengajaan

Layanan NTP tersebar pada banyak server di internet Server utama tersambung langsung

ke sumber waktu seperti penerima sinyal radio UTC Server sekunder disinkronisasi dengan

server primer Server-servernya tersambung dalam hierarkikal logika yang disebut

synchronization subnet seperti Gambar 3 Semakin keatas levelnya akan semakin akurat clock-

nya Galat terjadi setiap melewati satu level Server-server NTP bersinkronasi satu sama lain

dengan tiga cara antara lain multicast procedure-call dan symmetric

1 Multicast ditujukan untuk LAN berkecepatan tinggi Satu atau lebih server secara periodik

menyebar waktu clock ke server di komputer lain yang tersambung di LAN Mode ini akurasinya

rendah tetapi cocok untuk berbagai kepentingan

2 Procedure-call hampir sama dengan algoritma Cristian Server menerima request dari

komputer lain dan membalasnya dengan pembacaan clock saat pengiriman Mode ini cocok

ketika keakurasian tinggi dibutuhkan atau ketika multicast tidak dappat dilakukan

3 Mode symmetric ditujukan untuk server yang mensuplai waktu dalam LAN atau pada level

tertinggi dari sebuah synchronization subnet

Pada mode procedure-call dan symmetric mode memroses pertukaran bagian-bagian

pesan Tiap pesan memiliki catatan waktu dari peristiwa yang baru saja terjadi yaitu waktu local

ketika pesan tersebut dikirimkan Seperti pada Gambar 4 pesan m menyimpan catatan waktu

setiap akan ditransmisikan yaitu Ti-3 dan Ti-1 dan ketika diterima yaitu Ti-2 dan Ti

Kemudian NTP menghitung jeda waktu antara dua clock komputer

3 Logical Time and Logical Clock

Dari sudut pandang dari setiap single proses event-event diurutkan berdasakan waktu

seperti pada local clock Tetapi seperti yang dikatakan oleh Lamport [1978] kita tidak dapat

melakukan singkronisasi clock secara sempurna pada sebuah sistem terdistribusi Kita tidak

dapat secara umum menggunakan physical time untuk menentukan urutan dari suatu event yang

terjadi Secara umum kita dapat menggunakan sebuah skema yang mirip dengan physical tapi

pada sistem terdistribusi digunakan untuk mengurutkan event-event yang terjadi pada proses

yang berbeda Pengurutan ini berdasarkan pada dua hal yang simple dan intuitif

Jika dua event terjadi bersamaam pada satu process yang sama pi (i = 12 hellip N) kemudian

event-event tersebut terjadi sesuai dengan urutan pi yang kita sebutkan diatas

Kapan saja sebuah message dikirim diantara proses-proses event dari pengiriman message

terjadi sebelum event dari penerimaan message

Lamport menyebutkan partial ordering diperoleh dengan men-generalalisasikan kedua hubungan

ini relasi happened-before Istilah ini biasa juga disebut causal ordering atau potential causal

ordering Kita dapat mendefinisikan relasi happened-before dinotasikan dengan 1048890 seperti

berikut

HB1 Jika ᴲ process pi e iersquo maka e ersquo

HB2 untuk setiap message m send(m) receive(m)

- Dimana send(m) adalah event dari pengiriman message dan receive(m) adalah event dari

penerimaan message

HB3 Jika e ersquo dan erdquo adalah event dimana e ersquo dan ersquo erdquo maka e erdquo

Relasi diilustrasikan pada gambar 5 Pada ketiga proses tersebut dapat dikombinasikan

menjadi a f Antar a dan e tidak ada relasi maka ditulis a e

31 Logical Clocks

Lamport menemukan sebuah mekanisme yang simple untuk mengurutkan happened-

before secara numeris Mekanisme ini disebut logical clock Lamport logical clock adalah

software counter yang bertambah secara monoton dimana nilainya tidak perlu menanggung

hubungan tertentu ke suatu physical clock Setiap proses pi tetap berada pada logical clock

masing-masing Timestamp dari suatu event e pada pi disini dinotasikan dengan Li(e) dan L(e)

Untuk notasi dalam suatu prose adalah sebagai berikut

LC 1 Li bertambah sebelum setiap event muncul pada proses pi Li = Li + 1

LC 2 (a) Ketika sebuah proses pi mengirim sebuah message m nilai L juga ditempelkan pada

nilai m t = Li

(b) pada saat menerima pesan (mt) sebuah proses pj menghitung L j = max(Lj t) dan lalu

mengaplikasikan LC1 sebelum melakukan timestamp untuk event receive(m)

32 Totally ordered logical clocks

Beberapa pasang event yang berbeda yang dihasilkan oleh proses yang berbeda telah

diidentifikasi dengan Lamport timestamp secara numeris Namun kita dapat menciptakan sebuah

urutan total peristiwa yaitu satu untuk yang semua pasangan dari event yang berbeda terjadi

Jika e adalah sebuah peristiwa yang terjadi di pi dengan local timestamp Ti dan e adalah sebuah

event yang terjadi di pj dengan local timestamp Tj kita mendefinisikan global logic timestamp

untuk event ini menjadi (Ti i) dan (Tj j) Dan kita define (Ti i) lt(Tj j) jika hanya jika salah Ti

ltTj atau Ti = Tj dan i ltj terpenuhi Urutan ini tidak memiliki arti fisik umum (karena

pengidentifikasi proses yang tidak beraturan) tetapi kadang-kadang berguna Lamport

menggunakannya misalnya untuk mengurutkan proses masuknya ke bagian kritis

33 Vector clocks

Mattern [1989] dan Fidge [1991] mengembangkan vector clocks untuk mengatasi

kekurangan pada Lamport clocks fakta bahwa dari L(e) lt L(ersquo) kita tidak dapat menyimpulkan

bahwa e ersquo Vektor clock untuk sebuah sistem dari N proses adalah sebuah array dari N

integer Setiap proses berada pada vektor clock Vi masing-masing Aturan adalah sebagai berikut

VC1 Inisialisasi Vi [j] = 0 for ij = 12hellip N

VC2 sesaat sebelum pi men-timestamp sebuah event diset Vi[i] = Vi[i] + 1

VC3 pi memasukan nilai t = Vi pada setiap message yang diirim

VC4 Ketika pi menarima sebuah timestamp t pada sebuah sebuah message pi di set Vi[j] =

max(Vi[j] t[j]) for j = 12hellipN

DAFTAR PUSTAKA

Herusetyo Arif Time and Global State UGM Publisher Yogyakarta

2006

L Lamport Time Clocks And The Ordering Of Events In A Distributed

System Computer Science Laboratory SRI International Massachusett

1990

Coulouris George Distributed System Concept and Design Addison

Press Wesley 2001

12 Clock Skew And Clock Drift

Clock milik tiap-tiap komputer tidak selalu sama Perbedaan antara pembacaan dua clock

komputer berbeda disebut skew Sedangkan perbedaan clock rate disebut clock drift Pada clock

fisik osilasi frekuensi dan temperatur mempengaruhi perbedaan clock tiap komputer

Perbedaannya mungkin sangat kecil tetapi akumulasi perbedaan tersebut dapat mencapai tahap

yang bisa diamati dengan mata telanjang walaupun sudah disamakan nilainya Clock drift rate

adalah perubahan perbedaan pembacaan antara clock dan perfect reference clock (clock yang

dijadikan acuan)

13 Waktu Universal Terkoordinasi (Coordinated Universal Time)

Clock komputer dapat disinkronkan dengan clock luar yang akurasinya tinggi Clock

yang akurasinya paling tinggi menggunakan osilator atom Keluaran clock ini digunakan sebagai

standar waktu international Coordinated Universal Time (UTC) adalah standar internasional

untuk penjagaan waktu (timekeeping) Sinyal UTC disiarkan dari stasiun radio dan satelit ke

seluruh dunia Komputer dengan penerima sinyal di seluruh dunia dapat mensinkronkan

clocknya dengan sinyal ini

2 Sinkronasi Clock Fisik

Untuk mengetahui kapan sebuah peristiwa terjadi secara akurat pada proses system

terdistribusi diperlukan sinkronisasi dengan sumber waktu dari luar yang disebut sinkronisasi

eksternal (external synchronization) Dan jika satu clock tersinkronisasi dengan clock yang lain

dengan derajat akurasi yang diketahui maka kita bisa mengukur interval terjadinya dua peristiwa

pada komputer yang berbeda walaupun tidak tersinkronisasi ke sumber waktu dari luar Hal ini

disebut sinkronisasi internal (internal synchronization)

Beberapa gagasan pengkoreksian (correctness) untuk clock sudah pernah diajukan

Hardware clock H selalu dikoreksi apabila drift-nya sudah mencapai angka tertentu (ρ gt 0) Jadi

galat (error) perhitungan interval antara waktu sebenarnya t dan trsquo (t gt trsquo) adalah

(1 - ρ)(t - t) le H(t) - H(t) le (1 + ρ)(t -t)

Clock yang tidak menerima pengkoreksian apapun dinyatakan faulty Clock dinyatakan crash

failure ketika berhenti berdetik sama sekali Kegagalan clock lainnya adalah arbitrary failure

Contoh arbitrary failure adalah lsquoY2K bugrsquo yang terjadi pada pergantian tahun 1999 ke 2000

Setelah 31 Desember 1999 dilanjutkan ke 1 Januari 1900 Catatan clock tidak harus akurat

untuk menjadi benar

21 Sinkronisasi pada Sistem Sinkron

Pada sistem sinkron sebuah proses mengirim waktu t dari clock lokalnya ke proses

lainnya dalam pesan m Proses seharusnya menerima dan mencocokkannya dengan clock

lokalnya sendiri dengan t + Ttrans di mana Ttrans adalah waktu transmisi Sayangnya Ttrans

bervariasi dan sulit diketahui Namun waktu minimal transmisi min tetap dapat diperkirakan

apabila jaringan lancar dan tidak ada proses lain yang berjalan bersamaan Sistem terdistribusi

yang banyak digunakan adalah asinkron Delay pesan tidak terbatas atau tergantung masing-

masing clock komputer Pada sistem asinkron Ttrans = min + x di mana x ge 0 Nilai x tidak

diketahui tetapi dapat diukur

22 Metode Cristian untuk Sinkronisasi Clock

Cristian menyarankan untuk menggunakan server yang menerima sinyal UTC untuk

mensiknronisasikan komputer secara eksternal Sebuah proses p meminta waktu dalam pesan m

kepada server S kemudian menerima nilai waktu t dalam pesan mt Proses p merekam total

waktu yang dibutuhkan Tround untuk mengirim permintaan dan menerima balasan Dengan

begini waktu yang akurat dapat diperhitungkan Permasalahannya adalah server yang

menyimpan waktu hanya satu yang apabila gagal maka untuk sementara waktu sinkronisasi

tidak dapat dilakukan Cristian menyarankan untuk menggunakan beberapa server yang sudah

tersinkronasi Jadi klien meminta ke semua server dan hanya menggunakan balasan yang

pertama kali diterima

23 Algoritma Berkeley

Gusella dan Zatti mengembangkan algoritma untuk sinkronisasi internal Mereka

mengembangkan algoritma ini pada komputer berbasis Barkeley UNIX Pada lagoritma ini

sebuah komputer ditunjuk sebagai coordinator yang disebut master Komputer ini kemudian

memilih komputer-komputer untuk dimintai sinkronisasi yang disebut slave dengan master

secara periodik Slave-slave membalas dengan nilai clock miliknya Master menghitung

clocknya sendiri dengan memperhitungkan waktu perjalanan data dan rata-rata dari nilai clock

yang didapat Algoritma ini tidak akan membaca clock yang faulty Clock yang hanya berbeda

sedikit dengan jumlah tertentu dengan clock lainnya yang dipilih untuk dirata-rata Hal ini

disebut fault tolerant average Sehingga ketika ada satu clock yang gagal atau rusak tidak

mempengaruhi clock Master

24 Protokol Waktu Jaringan (Network Time Protocol)

Metode Cristian dan algoritma Berkeley pada dasarnya digunakan untuk komunikasi

intranet Protokol Waktu Jaringan (NTP) mendefinisikan arsitektur untuk pelayanan waktu dan

protocol untuk distribusi informasi waktu lewat internet Tujuan dan fitur NTP antara lain

Untuk menyediakan layanan yang memungkinkan klien di Internet yang akan disinkronkan akurat

UTC

Untuk menyediakan layanan yang bisa bertahan di jaringan mengalami loss karena jarak

Untuk mengaktifkan klien untuk mensinkronisasi cukup sering untuk mengimbangi tingkat drift

ditemukan di kebanyakan komputer NTP

Untuk menyediakan perlindungan terhadap interferensi dari layanan waktu baik galat

maupun ketidaksengajaan

Layanan NTP tersebar pada banyak server di internet Server utama tersambung langsung

ke sumber waktu seperti penerima sinyal radio UTC Server sekunder disinkronisasi dengan

server primer Server-servernya tersambung dalam hierarkikal logika yang disebut

synchronization subnet seperti Gambar 3 Semakin keatas levelnya akan semakin akurat clock-

nya Galat terjadi setiap melewati satu level Server-server NTP bersinkronasi satu sama lain

dengan tiga cara antara lain multicast procedure-call dan symmetric

1 Multicast ditujukan untuk LAN berkecepatan tinggi Satu atau lebih server secara periodik

menyebar waktu clock ke server di komputer lain yang tersambung di LAN Mode ini akurasinya

rendah tetapi cocok untuk berbagai kepentingan

2 Procedure-call hampir sama dengan algoritma Cristian Server menerima request dari

komputer lain dan membalasnya dengan pembacaan clock saat pengiriman Mode ini cocok

ketika keakurasian tinggi dibutuhkan atau ketika multicast tidak dappat dilakukan

3 Mode symmetric ditujukan untuk server yang mensuplai waktu dalam LAN atau pada level

tertinggi dari sebuah synchronization subnet

Pada mode procedure-call dan symmetric mode memroses pertukaran bagian-bagian

pesan Tiap pesan memiliki catatan waktu dari peristiwa yang baru saja terjadi yaitu waktu local

ketika pesan tersebut dikirimkan Seperti pada Gambar 4 pesan m menyimpan catatan waktu

setiap akan ditransmisikan yaitu Ti-3 dan Ti-1 dan ketika diterima yaitu Ti-2 dan Ti

Kemudian NTP menghitung jeda waktu antara dua clock komputer

3 Logical Time and Logical Clock

Dari sudut pandang dari setiap single proses event-event diurutkan berdasakan waktu

seperti pada local clock Tetapi seperti yang dikatakan oleh Lamport [1978] kita tidak dapat

melakukan singkronisasi clock secara sempurna pada sebuah sistem terdistribusi Kita tidak

dapat secara umum menggunakan physical time untuk menentukan urutan dari suatu event yang

terjadi Secara umum kita dapat menggunakan sebuah skema yang mirip dengan physical tapi

pada sistem terdistribusi digunakan untuk mengurutkan event-event yang terjadi pada proses

yang berbeda Pengurutan ini berdasarkan pada dua hal yang simple dan intuitif

Jika dua event terjadi bersamaam pada satu process yang sama pi (i = 12 hellip N) kemudian

event-event tersebut terjadi sesuai dengan urutan pi yang kita sebutkan diatas

Kapan saja sebuah message dikirim diantara proses-proses event dari pengiriman message

terjadi sebelum event dari penerimaan message

Lamport menyebutkan partial ordering diperoleh dengan men-generalalisasikan kedua hubungan

ini relasi happened-before Istilah ini biasa juga disebut causal ordering atau potential causal

ordering Kita dapat mendefinisikan relasi happened-before dinotasikan dengan 1048890 seperti

berikut

HB1 Jika ᴲ process pi e iersquo maka e ersquo

HB2 untuk setiap message m send(m) receive(m)

- Dimana send(m) adalah event dari pengiriman message dan receive(m) adalah event dari

penerimaan message

HB3 Jika e ersquo dan erdquo adalah event dimana e ersquo dan ersquo erdquo maka e erdquo

Relasi diilustrasikan pada gambar 5 Pada ketiga proses tersebut dapat dikombinasikan

menjadi a f Antar a dan e tidak ada relasi maka ditulis a e

31 Logical Clocks

Lamport menemukan sebuah mekanisme yang simple untuk mengurutkan happened-

before secara numeris Mekanisme ini disebut logical clock Lamport logical clock adalah

software counter yang bertambah secara monoton dimana nilainya tidak perlu menanggung

hubungan tertentu ke suatu physical clock Setiap proses pi tetap berada pada logical clock

masing-masing Timestamp dari suatu event e pada pi disini dinotasikan dengan Li(e) dan L(e)

Untuk notasi dalam suatu prose adalah sebagai berikut

LC 1 Li bertambah sebelum setiap event muncul pada proses pi Li = Li + 1

LC 2 (a) Ketika sebuah proses pi mengirim sebuah message m nilai L juga ditempelkan pada

nilai m t = Li

(b) pada saat menerima pesan (mt) sebuah proses pj menghitung L j = max(Lj t) dan lalu

mengaplikasikan LC1 sebelum melakukan timestamp untuk event receive(m)

32 Totally ordered logical clocks

Beberapa pasang event yang berbeda yang dihasilkan oleh proses yang berbeda telah

diidentifikasi dengan Lamport timestamp secara numeris Namun kita dapat menciptakan sebuah

urutan total peristiwa yaitu satu untuk yang semua pasangan dari event yang berbeda terjadi

Jika e adalah sebuah peristiwa yang terjadi di pi dengan local timestamp Ti dan e adalah sebuah

event yang terjadi di pj dengan local timestamp Tj kita mendefinisikan global logic timestamp

untuk event ini menjadi (Ti i) dan (Tj j) Dan kita define (Ti i) lt(Tj j) jika hanya jika salah Ti

ltTj atau Ti = Tj dan i ltj terpenuhi Urutan ini tidak memiliki arti fisik umum (karena

pengidentifikasi proses yang tidak beraturan) tetapi kadang-kadang berguna Lamport

menggunakannya misalnya untuk mengurutkan proses masuknya ke bagian kritis

33 Vector clocks

Mattern [1989] dan Fidge [1991] mengembangkan vector clocks untuk mengatasi

kekurangan pada Lamport clocks fakta bahwa dari L(e) lt L(ersquo) kita tidak dapat menyimpulkan

bahwa e ersquo Vektor clock untuk sebuah sistem dari N proses adalah sebuah array dari N

integer Setiap proses berada pada vektor clock Vi masing-masing Aturan adalah sebagai berikut

VC1 Inisialisasi Vi [j] = 0 for ij = 12hellip N

VC2 sesaat sebelum pi men-timestamp sebuah event diset Vi[i] = Vi[i] + 1

VC3 pi memasukan nilai t = Vi pada setiap message yang diirim

VC4 Ketika pi menarima sebuah timestamp t pada sebuah sebuah message pi di set Vi[j] =

max(Vi[j] t[j]) for j = 12hellipN

DAFTAR PUSTAKA

Herusetyo Arif Time and Global State UGM Publisher Yogyakarta

2006

L Lamport Time Clocks And The Ordering Of Events In A Distributed

System Computer Science Laboratory SRI International Massachusett

1990

Coulouris George Distributed System Concept and Design Addison

Press Wesley 2001

Untuk mengetahui kapan sebuah peristiwa terjadi secara akurat pada proses system

terdistribusi diperlukan sinkronisasi dengan sumber waktu dari luar yang disebut sinkronisasi

eksternal (external synchronization) Dan jika satu clock tersinkronisasi dengan clock yang lain

dengan derajat akurasi yang diketahui maka kita bisa mengukur interval terjadinya dua peristiwa

pada komputer yang berbeda walaupun tidak tersinkronisasi ke sumber waktu dari luar Hal ini

disebut sinkronisasi internal (internal synchronization)

Beberapa gagasan pengkoreksian (correctness) untuk clock sudah pernah diajukan

Hardware clock H selalu dikoreksi apabila drift-nya sudah mencapai angka tertentu (ρ gt 0) Jadi

galat (error) perhitungan interval antara waktu sebenarnya t dan trsquo (t gt trsquo) adalah

(1 - ρ)(t - t) le H(t) - H(t) le (1 + ρ)(t -t)

Clock yang tidak menerima pengkoreksian apapun dinyatakan faulty Clock dinyatakan crash

failure ketika berhenti berdetik sama sekali Kegagalan clock lainnya adalah arbitrary failure

Contoh arbitrary failure adalah lsquoY2K bugrsquo yang terjadi pada pergantian tahun 1999 ke 2000

Setelah 31 Desember 1999 dilanjutkan ke 1 Januari 1900 Catatan clock tidak harus akurat

untuk menjadi benar

21 Sinkronisasi pada Sistem Sinkron

Pada sistem sinkron sebuah proses mengirim waktu t dari clock lokalnya ke proses

lainnya dalam pesan m Proses seharusnya menerima dan mencocokkannya dengan clock

lokalnya sendiri dengan t + Ttrans di mana Ttrans adalah waktu transmisi Sayangnya Ttrans

bervariasi dan sulit diketahui Namun waktu minimal transmisi min tetap dapat diperkirakan

apabila jaringan lancar dan tidak ada proses lain yang berjalan bersamaan Sistem terdistribusi

yang banyak digunakan adalah asinkron Delay pesan tidak terbatas atau tergantung masing-

masing clock komputer Pada sistem asinkron Ttrans = min + x di mana x ge 0 Nilai x tidak

diketahui tetapi dapat diukur

22 Metode Cristian untuk Sinkronisasi Clock

Cristian menyarankan untuk menggunakan server yang menerima sinyal UTC untuk

mensiknronisasikan komputer secara eksternal Sebuah proses p meminta waktu dalam pesan m

kepada server S kemudian menerima nilai waktu t dalam pesan mt Proses p merekam total

waktu yang dibutuhkan Tround untuk mengirim permintaan dan menerima balasan Dengan

begini waktu yang akurat dapat diperhitungkan Permasalahannya adalah server yang

menyimpan waktu hanya satu yang apabila gagal maka untuk sementara waktu sinkronisasi

tidak dapat dilakukan Cristian menyarankan untuk menggunakan beberapa server yang sudah

tersinkronasi Jadi klien meminta ke semua server dan hanya menggunakan balasan yang

pertama kali diterima

23 Algoritma Berkeley

Gusella dan Zatti mengembangkan algoritma untuk sinkronisasi internal Mereka

mengembangkan algoritma ini pada komputer berbasis Barkeley UNIX Pada lagoritma ini

sebuah komputer ditunjuk sebagai coordinator yang disebut master Komputer ini kemudian

memilih komputer-komputer untuk dimintai sinkronisasi yang disebut slave dengan master

secara periodik Slave-slave membalas dengan nilai clock miliknya Master menghitung

clocknya sendiri dengan memperhitungkan waktu perjalanan data dan rata-rata dari nilai clock

yang didapat Algoritma ini tidak akan membaca clock yang faulty Clock yang hanya berbeda

sedikit dengan jumlah tertentu dengan clock lainnya yang dipilih untuk dirata-rata Hal ini

disebut fault tolerant average Sehingga ketika ada satu clock yang gagal atau rusak tidak

mempengaruhi clock Master

24 Protokol Waktu Jaringan (Network Time Protocol)

Metode Cristian dan algoritma Berkeley pada dasarnya digunakan untuk komunikasi

intranet Protokol Waktu Jaringan (NTP) mendefinisikan arsitektur untuk pelayanan waktu dan

protocol untuk distribusi informasi waktu lewat internet Tujuan dan fitur NTP antara lain

Untuk menyediakan layanan yang memungkinkan klien di Internet yang akan disinkronkan akurat

UTC

Untuk menyediakan layanan yang bisa bertahan di jaringan mengalami loss karena jarak

Untuk mengaktifkan klien untuk mensinkronisasi cukup sering untuk mengimbangi tingkat drift

ditemukan di kebanyakan komputer NTP

Untuk menyediakan perlindungan terhadap interferensi dari layanan waktu baik galat

maupun ketidaksengajaan

Layanan NTP tersebar pada banyak server di internet Server utama tersambung langsung

ke sumber waktu seperti penerima sinyal radio UTC Server sekunder disinkronisasi dengan

server primer Server-servernya tersambung dalam hierarkikal logika yang disebut

synchronization subnet seperti Gambar 3 Semakin keatas levelnya akan semakin akurat clock-

nya Galat terjadi setiap melewati satu level Server-server NTP bersinkronasi satu sama lain

dengan tiga cara antara lain multicast procedure-call dan symmetric

1 Multicast ditujukan untuk LAN berkecepatan tinggi Satu atau lebih server secara periodik

menyebar waktu clock ke server di komputer lain yang tersambung di LAN Mode ini akurasinya

rendah tetapi cocok untuk berbagai kepentingan

2 Procedure-call hampir sama dengan algoritma Cristian Server menerima request dari

komputer lain dan membalasnya dengan pembacaan clock saat pengiriman Mode ini cocok

ketika keakurasian tinggi dibutuhkan atau ketika multicast tidak dappat dilakukan

3 Mode symmetric ditujukan untuk server yang mensuplai waktu dalam LAN atau pada level

tertinggi dari sebuah synchronization subnet

Pada mode procedure-call dan symmetric mode memroses pertukaran bagian-bagian

pesan Tiap pesan memiliki catatan waktu dari peristiwa yang baru saja terjadi yaitu waktu local

ketika pesan tersebut dikirimkan Seperti pada Gambar 4 pesan m menyimpan catatan waktu

setiap akan ditransmisikan yaitu Ti-3 dan Ti-1 dan ketika diterima yaitu Ti-2 dan Ti

Kemudian NTP menghitung jeda waktu antara dua clock komputer

3 Logical Time and Logical Clock

Dari sudut pandang dari setiap single proses event-event diurutkan berdasakan waktu

seperti pada local clock Tetapi seperti yang dikatakan oleh Lamport [1978] kita tidak dapat

melakukan singkronisasi clock secara sempurna pada sebuah sistem terdistribusi Kita tidak

dapat secara umum menggunakan physical time untuk menentukan urutan dari suatu event yang

terjadi Secara umum kita dapat menggunakan sebuah skema yang mirip dengan physical tapi

pada sistem terdistribusi digunakan untuk mengurutkan event-event yang terjadi pada proses

yang berbeda Pengurutan ini berdasarkan pada dua hal yang simple dan intuitif

Jika dua event terjadi bersamaam pada satu process yang sama pi (i = 12 hellip N) kemudian

event-event tersebut terjadi sesuai dengan urutan pi yang kita sebutkan diatas

Kapan saja sebuah message dikirim diantara proses-proses event dari pengiriman message

terjadi sebelum event dari penerimaan message

Lamport menyebutkan partial ordering diperoleh dengan men-generalalisasikan kedua hubungan

ini relasi happened-before Istilah ini biasa juga disebut causal ordering atau potential causal

ordering Kita dapat mendefinisikan relasi happened-before dinotasikan dengan 1048890 seperti

berikut

HB1 Jika ᴲ process pi e iersquo maka e ersquo

HB2 untuk setiap message m send(m) receive(m)

- Dimana send(m) adalah event dari pengiriman message dan receive(m) adalah event dari

penerimaan message

HB3 Jika e ersquo dan erdquo adalah event dimana e ersquo dan ersquo erdquo maka e erdquo

Relasi diilustrasikan pada gambar 5 Pada ketiga proses tersebut dapat dikombinasikan

menjadi a f Antar a dan e tidak ada relasi maka ditulis a e

31 Logical Clocks

Lamport menemukan sebuah mekanisme yang simple untuk mengurutkan happened-

before secara numeris Mekanisme ini disebut logical clock Lamport logical clock adalah

software counter yang bertambah secara monoton dimana nilainya tidak perlu menanggung

hubungan tertentu ke suatu physical clock Setiap proses pi tetap berada pada logical clock

masing-masing Timestamp dari suatu event e pada pi disini dinotasikan dengan Li(e) dan L(e)

Untuk notasi dalam suatu prose adalah sebagai berikut

LC 1 Li bertambah sebelum setiap event muncul pada proses pi Li = Li + 1

LC 2 (a) Ketika sebuah proses pi mengirim sebuah message m nilai L juga ditempelkan pada

nilai m t = Li

(b) pada saat menerima pesan (mt) sebuah proses pj menghitung L j = max(Lj t) dan lalu

mengaplikasikan LC1 sebelum melakukan timestamp untuk event receive(m)

32 Totally ordered logical clocks

Beberapa pasang event yang berbeda yang dihasilkan oleh proses yang berbeda telah

diidentifikasi dengan Lamport timestamp secara numeris Namun kita dapat menciptakan sebuah

urutan total peristiwa yaitu satu untuk yang semua pasangan dari event yang berbeda terjadi

Jika e adalah sebuah peristiwa yang terjadi di pi dengan local timestamp Ti dan e adalah sebuah

event yang terjadi di pj dengan local timestamp Tj kita mendefinisikan global logic timestamp

untuk event ini menjadi (Ti i) dan (Tj j) Dan kita define (Ti i) lt(Tj j) jika hanya jika salah Ti

ltTj atau Ti = Tj dan i ltj terpenuhi Urutan ini tidak memiliki arti fisik umum (karena

pengidentifikasi proses yang tidak beraturan) tetapi kadang-kadang berguna Lamport

menggunakannya misalnya untuk mengurutkan proses masuknya ke bagian kritis

33 Vector clocks

Mattern [1989] dan Fidge [1991] mengembangkan vector clocks untuk mengatasi

kekurangan pada Lamport clocks fakta bahwa dari L(e) lt L(ersquo) kita tidak dapat menyimpulkan

bahwa e ersquo Vektor clock untuk sebuah sistem dari N proses adalah sebuah array dari N

integer Setiap proses berada pada vektor clock Vi masing-masing Aturan adalah sebagai berikut

VC1 Inisialisasi Vi [j] = 0 for ij = 12hellip N

VC2 sesaat sebelum pi men-timestamp sebuah event diset Vi[i] = Vi[i] + 1

VC3 pi memasukan nilai t = Vi pada setiap message yang diirim

VC4 Ketika pi menarima sebuah timestamp t pada sebuah sebuah message pi di set Vi[j] =

max(Vi[j] t[j]) for j = 12hellipN

DAFTAR PUSTAKA

Herusetyo Arif Time and Global State UGM Publisher Yogyakarta

2006

L Lamport Time Clocks And The Ordering Of Events In A Distributed

System Computer Science Laboratory SRI International Massachusett

1990

Coulouris George Distributed System Concept and Design Addison

Press Wesley 2001

Cristian menyarankan untuk menggunakan server yang menerima sinyal UTC untuk

mensiknronisasikan komputer secara eksternal Sebuah proses p meminta waktu dalam pesan m

kepada server S kemudian menerima nilai waktu t dalam pesan mt Proses p merekam total

waktu yang dibutuhkan Tround untuk mengirim permintaan dan menerima balasan Dengan

begini waktu yang akurat dapat diperhitungkan Permasalahannya adalah server yang

menyimpan waktu hanya satu yang apabila gagal maka untuk sementara waktu sinkronisasi

tidak dapat dilakukan Cristian menyarankan untuk menggunakan beberapa server yang sudah

tersinkronasi Jadi klien meminta ke semua server dan hanya menggunakan balasan yang

pertama kali diterima

23 Algoritma Berkeley

Gusella dan Zatti mengembangkan algoritma untuk sinkronisasi internal Mereka

mengembangkan algoritma ini pada komputer berbasis Barkeley UNIX Pada lagoritma ini

sebuah komputer ditunjuk sebagai coordinator yang disebut master Komputer ini kemudian

memilih komputer-komputer untuk dimintai sinkronisasi yang disebut slave dengan master

secara periodik Slave-slave membalas dengan nilai clock miliknya Master menghitung

clocknya sendiri dengan memperhitungkan waktu perjalanan data dan rata-rata dari nilai clock

yang didapat Algoritma ini tidak akan membaca clock yang faulty Clock yang hanya berbeda

sedikit dengan jumlah tertentu dengan clock lainnya yang dipilih untuk dirata-rata Hal ini

disebut fault tolerant average Sehingga ketika ada satu clock yang gagal atau rusak tidak

mempengaruhi clock Master

24 Protokol Waktu Jaringan (Network Time Protocol)

Metode Cristian dan algoritma Berkeley pada dasarnya digunakan untuk komunikasi

intranet Protokol Waktu Jaringan (NTP) mendefinisikan arsitektur untuk pelayanan waktu dan

protocol untuk distribusi informasi waktu lewat internet Tujuan dan fitur NTP antara lain

Untuk menyediakan layanan yang memungkinkan klien di Internet yang akan disinkronkan akurat

UTC

Untuk menyediakan layanan yang bisa bertahan di jaringan mengalami loss karena jarak

Untuk mengaktifkan klien untuk mensinkronisasi cukup sering untuk mengimbangi tingkat drift

ditemukan di kebanyakan komputer NTP

Untuk menyediakan perlindungan terhadap interferensi dari layanan waktu baik galat

maupun ketidaksengajaan

Layanan NTP tersebar pada banyak server di internet Server utama tersambung langsung

ke sumber waktu seperti penerima sinyal radio UTC Server sekunder disinkronisasi dengan

server primer Server-servernya tersambung dalam hierarkikal logika yang disebut

synchronization subnet seperti Gambar 3 Semakin keatas levelnya akan semakin akurat clock-

nya Galat terjadi setiap melewati satu level Server-server NTP bersinkronasi satu sama lain

dengan tiga cara antara lain multicast procedure-call dan symmetric

1 Multicast ditujukan untuk LAN berkecepatan tinggi Satu atau lebih server secara periodik

menyebar waktu clock ke server di komputer lain yang tersambung di LAN Mode ini akurasinya

rendah tetapi cocok untuk berbagai kepentingan

2 Procedure-call hampir sama dengan algoritma Cristian Server menerima request dari

komputer lain dan membalasnya dengan pembacaan clock saat pengiriman Mode ini cocok

ketika keakurasian tinggi dibutuhkan atau ketika multicast tidak dappat dilakukan

3 Mode symmetric ditujukan untuk server yang mensuplai waktu dalam LAN atau pada level

tertinggi dari sebuah synchronization subnet

Pada mode procedure-call dan symmetric mode memroses pertukaran bagian-bagian

pesan Tiap pesan memiliki catatan waktu dari peristiwa yang baru saja terjadi yaitu waktu local

ketika pesan tersebut dikirimkan Seperti pada Gambar 4 pesan m menyimpan catatan waktu

setiap akan ditransmisikan yaitu Ti-3 dan Ti-1 dan ketika diterima yaitu Ti-2 dan Ti

Kemudian NTP menghitung jeda waktu antara dua clock komputer

3 Logical Time and Logical Clock

Dari sudut pandang dari setiap single proses event-event diurutkan berdasakan waktu

seperti pada local clock Tetapi seperti yang dikatakan oleh Lamport [1978] kita tidak dapat

melakukan singkronisasi clock secara sempurna pada sebuah sistem terdistribusi Kita tidak

dapat secara umum menggunakan physical time untuk menentukan urutan dari suatu event yang

terjadi Secara umum kita dapat menggunakan sebuah skema yang mirip dengan physical tapi

pada sistem terdistribusi digunakan untuk mengurutkan event-event yang terjadi pada proses

yang berbeda Pengurutan ini berdasarkan pada dua hal yang simple dan intuitif

Jika dua event terjadi bersamaam pada satu process yang sama pi (i = 12 hellip N) kemudian

event-event tersebut terjadi sesuai dengan urutan pi yang kita sebutkan diatas

Kapan saja sebuah message dikirim diantara proses-proses event dari pengiriman message

terjadi sebelum event dari penerimaan message

Lamport menyebutkan partial ordering diperoleh dengan men-generalalisasikan kedua hubungan

ini relasi happened-before Istilah ini biasa juga disebut causal ordering atau potential causal

ordering Kita dapat mendefinisikan relasi happened-before dinotasikan dengan 1048890 seperti

berikut

HB1 Jika ᴲ process pi e iersquo maka e ersquo

HB2 untuk setiap message m send(m) receive(m)

- Dimana send(m) adalah event dari pengiriman message dan receive(m) adalah event dari

penerimaan message

HB3 Jika e ersquo dan erdquo adalah event dimana e ersquo dan ersquo erdquo maka e erdquo

Relasi diilustrasikan pada gambar 5 Pada ketiga proses tersebut dapat dikombinasikan

menjadi a f Antar a dan e tidak ada relasi maka ditulis a e

31 Logical Clocks

Lamport menemukan sebuah mekanisme yang simple untuk mengurutkan happened-

before secara numeris Mekanisme ini disebut logical clock Lamport logical clock adalah

software counter yang bertambah secara monoton dimana nilainya tidak perlu menanggung

hubungan tertentu ke suatu physical clock Setiap proses pi tetap berada pada logical clock

masing-masing Timestamp dari suatu event e pada pi disini dinotasikan dengan Li(e) dan L(e)

Untuk notasi dalam suatu prose adalah sebagai berikut

LC 1 Li bertambah sebelum setiap event muncul pada proses pi Li = Li + 1

LC 2 (a) Ketika sebuah proses pi mengirim sebuah message m nilai L juga ditempelkan pada

nilai m t = Li

(b) pada saat menerima pesan (mt) sebuah proses pj menghitung L j = max(Lj t) dan lalu

mengaplikasikan LC1 sebelum melakukan timestamp untuk event receive(m)

32 Totally ordered logical clocks

Beberapa pasang event yang berbeda yang dihasilkan oleh proses yang berbeda telah

diidentifikasi dengan Lamport timestamp secara numeris Namun kita dapat menciptakan sebuah

urutan total peristiwa yaitu satu untuk yang semua pasangan dari event yang berbeda terjadi

Jika e adalah sebuah peristiwa yang terjadi di pi dengan local timestamp Ti dan e adalah sebuah

event yang terjadi di pj dengan local timestamp Tj kita mendefinisikan global logic timestamp

untuk event ini menjadi (Ti i) dan (Tj j) Dan kita define (Ti i) lt(Tj j) jika hanya jika salah Ti

ltTj atau Ti = Tj dan i ltj terpenuhi Urutan ini tidak memiliki arti fisik umum (karena

pengidentifikasi proses yang tidak beraturan) tetapi kadang-kadang berguna Lamport

menggunakannya misalnya untuk mengurutkan proses masuknya ke bagian kritis

33 Vector clocks

Mattern [1989] dan Fidge [1991] mengembangkan vector clocks untuk mengatasi

kekurangan pada Lamport clocks fakta bahwa dari L(e) lt L(ersquo) kita tidak dapat menyimpulkan

bahwa e ersquo Vektor clock untuk sebuah sistem dari N proses adalah sebuah array dari N

integer Setiap proses berada pada vektor clock Vi masing-masing Aturan adalah sebagai berikut

VC1 Inisialisasi Vi [j] = 0 for ij = 12hellip N

VC2 sesaat sebelum pi men-timestamp sebuah event diset Vi[i] = Vi[i] + 1

VC3 pi memasukan nilai t = Vi pada setiap message yang diirim

VC4 Ketika pi menarima sebuah timestamp t pada sebuah sebuah message pi di set Vi[j] =

max(Vi[j] t[j]) for j = 12hellipN

DAFTAR PUSTAKA

Herusetyo Arif Time and Global State UGM Publisher Yogyakarta

2006

L Lamport Time Clocks And The Ordering Of Events In A Distributed

System Computer Science Laboratory SRI International Massachusett

1990

Coulouris George Distributed System Concept and Design Addison

Press Wesley 2001

Metode Cristian dan algoritma Berkeley pada dasarnya digunakan untuk komunikasi

intranet Protokol Waktu Jaringan (NTP) mendefinisikan arsitektur untuk pelayanan waktu dan

protocol untuk distribusi informasi waktu lewat internet Tujuan dan fitur NTP antara lain

Untuk menyediakan layanan yang memungkinkan klien di Internet yang akan disinkronkan akurat

UTC

Untuk menyediakan layanan yang bisa bertahan di jaringan mengalami loss karena jarak

Untuk mengaktifkan klien untuk mensinkronisasi cukup sering untuk mengimbangi tingkat drift

ditemukan di kebanyakan komputer NTP

Untuk menyediakan perlindungan terhadap interferensi dari layanan waktu baik galat

maupun ketidaksengajaan

Layanan NTP tersebar pada banyak server di internet Server utama tersambung langsung

ke sumber waktu seperti penerima sinyal radio UTC Server sekunder disinkronisasi dengan

server primer Server-servernya tersambung dalam hierarkikal logika yang disebut

synchronization subnet seperti Gambar 3 Semakin keatas levelnya akan semakin akurat clock-

nya Galat terjadi setiap melewati satu level Server-server NTP bersinkronasi satu sama lain

dengan tiga cara antara lain multicast procedure-call dan symmetric

1 Multicast ditujukan untuk LAN berkecepatan tinggi Satu atau lebih server secara periodik

menyebar waktu clock ke server di komputer lain yang tersambung di LAN Mode ini akurasinya

rendah tetapi cocok untuk berbagai kepentingan

2 Procedure-call hampir sama dengan algoritma Cristian Server menerima request dari

komputer lain dan membalasnya dengan pembacaan clock saat pengiriman Mode ini cocok

ketika keakurasian tinggi dibutuhkan atau ketika multicast tidak dappat dilakukan

3 Mode symmetric ditujukan untuk server yang mensuplai waktu dalam LAN atau pada level

tertinggi dari sebuah synchronization subnet

Pada mode procedure-call dan symmetric mode memroses pertukaran bagian-bagian

pesan Tiap pesan memiliki catatan waktu dari peristiwa yang baru saja terjadi yaitu waktu local

ketika pesan tersebut dikirimkan Seperti pada Gambar 4 pesan m menyimpan catatan waktu

setiap akan ditransmisikan yaitu Ti-3 dan Ti-1 dan ketika diterima yaitu Ti-2 dan Ti

Kemudian NTP menghitung jeda waktu antara dua clock komputer

3 Logical Time and Logical Clock

Dari sudut pandang dari setiap single proses event-event diurutkan berdasakan waktu

seperti pada local clock Tetapi seperti yang dikatakan oleh Lamport [1978] kita tidak dapat

melakukan singkronisasi clock secara sempurna pada sebuah sistem terdistribusi Kita tidak

dapat secara umum menggunakan physical time untuk menentukan urutan dari suatu event yang

terjadi Secara umum kita dapat menggunakan sebuah skema yang mirip dengan physical tapi

pada sistem terdistribusi digunakan untuk mengurutkan event-event yang terjadi pada proses

yang berbeda Pengurutan ini berdasarkan pada dua hal yang simple dan intuitif

Jika dua event terjadi bersamaam pada satu process yang sama pi (i = 12 hellip N) kemudian

event-event tersebut terjadi sesuai dengan urutan pi yang kita sebutkan diatas

Kapan saja sebuah message dikirim diantara proses-proses event dari pengiriman message

terjadi sebelum event dari penerimaan message

Lamport menyebutkan partial ordering diperoleh dengan men-generalalisasikan kedua hubungan

ini relasi happened-before Istilah ini biasa juga disebut causal ordering atau potential causal

ordering Kita dapat mendefinisikan relasi happened-before dinotasikan dengan 1048890 seperti

berikut

HB1 Jika ᴲ process pi e iersquo maka e ersquo

HB2 untuk setiap message m send(m) receive(m)

- Dimana send(m) adalah event dari pengiriman message dan receive(m) adalah event dari

penerimaan message

HB3 Jika e ersquo dan erdquo adalah event dimana e ersquo dan ersquo erdquo maka e erdquo

Relasi diilustrasikan pada gambar 5 Pada ketiga proses tersebut dapat dikombinasikan

menjadi a f Antar a dan e tidak ada relasi maka ditulis a e

31 Logical Clocks

Lamport menemukan sebuah mekanisme yang simple untuk mengurutkan happened-

before secara numeris Mekanisme ini disebut logical clock Lamport logical clock adalah

software counter yang bertambah secara monoton dimana nilainya tidak perlu menanggung

hubungan tertentu ke suatu physical clock Setiap proses pi tetap berada pada logical clock

masing-masing Timestamp dari suatu event e pada pi disini dinotasikan dengan Li(e) dan L(e)

Untuk notasi dalam suatu prose adalah sebagai berikut

LC 1 Li bertambah sebelum setiap event muncul pada proses pi Li = Li + 1

LC 2 (a) Ketika sebuah proses pi mengirim sebuah message m nilai L juga ditempelkan pada

nilai m t = Li

(b) pada saat menerima pesan (mt) sebuah proses pj menghitung L j = max(Lj t) dan lalu

mengaplikasikan LC1 sebelum melakukan timestamp untuk event receive(m)

32 Totally ordered logical clocks

Beberapa pasang event yang berbeda yang dihasilkan oleh proses yang berbeda telah

diidentifikasi dengan Lamport timestamp secara numeris Namun kita dapat menciptakan sebuah

urutan total peristiwa yaitu satu untuk yang semua pasangan dari event yang berbeda terjadi

Jika e adalah sebuah peristiwa yang terjadi di pi dengan local timestamp Ti dan e adalah sebuah

event yang terjadi di pj dengan local timestamp Tj kita mendefinisikan global logic timestamp

untuk event ini menjadi (Ti i) dan (Tj j) Dan kita define (Ti i) lt(Tj j) jika hanya jika salah Ti

ltTj atau Ti = Tj dan i ltj terpenuhi Urutan ini tidak memiliki arti fisik umum (karena

pengidentifikasi proses yang tidak beraturan) tetapi kadang-kadang berguna Lamport

menggunakannya misalnya untuk mengurutkan proses masuknya ke bagian kritis

33 Vector clocks

Mattern [1989] dan Fidge [1991] mengembangkan vector clocks untuk mengatasi

kekurangan pada Lamport clocks fakta bahwa dari L(e) lt L(ersquo) kita tidak dapat menyimpulkan

bahwa e ersquo Vektor clock untuk sebuah sistem dari N proses adalah sebuah array dari N

integer Setiap proses berada pada vektor clock Vi masing-masing Aturan adalah sebagai berikut

VC1 Inisialisasi Vi [j] = 0 for ij = 12hellip N

VC2 sesaat sebelum pi men-timestamp sebuah event diset Vi[i] = Vi[i] + 1

VC3 pi memasukan nilai t = Vi pada setiap message yang diirim

VC4 Ketika pi menarima sebuah timestamp t pada sebuah sebuah message pi di set Vi[j] =

max(Vi[j] t[j]) for j = 12hellipN

DAFTAR PUSTAKA

Herusetyo Arif Time and Global State UGM Publisher Yogyakarta

2006

L Lamport Time Clocks And The Ordering Of Events In A Distributed

System Computer Science Laboratory SRI International Massachusett

1990

Coulouris George Distributed System Concept and Design Addison

Press Wesley 2001

1 Multicast ditujukan untuk LAN berkecepatan tinggi Satu atau lebih server secara periodik

menyebar waktu clock ke server di komputer lain yang tersambung di LAN Mode ini akurasinya

rendah tetapi cocok untuk berbagai kepentingan

2 Procedure-call hampir sama dengan algoritma Cristian Server menerima request dari

komputer lain dan membalasnya dengan pembacaan clock saat pengiriman Mode ini cocok

ketika keakurasian tinggi dibutuhkan atau ketika multicast tidak dappat dilakukan

3 Mode symmetric ditujukan untuk server yang mensuplai waktu dalam LAN atau pada level

tertinggi dari sebuah synchronization subnet

Pada mode procedure-call dan symmetric mode memroses pertukaran bagian-bagian

pesan Tiap pesan memiliki catatan waktu dari peristiwa yang baru saja terjadi yaitu waktu local

ketika pesan tersebut dikirimkan Seperti pada Gambar 4 pesan m menyimpan catatan waktu

setiap akan ditransmisikan yaitu Ti-3 dan Ti-1 dan ketika diterima yaitu Ti-2 dan Ti

Kemudian NTP menghitung jeda waktu antara dua clock komputer

3 Logical Time and Logical Clock

Dari sudut pandang dari setiap single proses event-event diurutkan berdasakan waktu

seperti pada local clock Tetapi seperti yang dikatakan oleh Lamport [1978] kita tidak dapat

melakukan singkronisasi clock secara sempurna pada sebuah sistem terdistribusi Kita tidak

dapat secara umum menggunakan physical time untuk menentukan urutan dari suatu event yang

terjadi Secara umum kita dapat menggunakan sebuah skema yang mirip dengan physical tapi

pada sistem terdistribusi digunakan untuk mengurutkan event-event yang terjadi pada proses

yang berbeda Pengurutan ini berdasarkan pada dua hal yang simple dan intuitif

Jika dua event terjadi bersamaam pada satu process yang sama pi (i = 12 hellip N) kemudian

event-event tersebut terjadi sesuai dengan urutan pi yang kita sebutkan diatas

Kapan saja sebuah message dikirim diantara proses-proses event dari pengiriman message

terjadi sebelum event dari penerimaan message

Lamport menyebutkan partial ordering diperoleh dengan men-generalalisasikan kedua hubungan

ini relasi happened-before Istilah ini biasa juga disebut causal ordering atau potential causal

ordering Kita dapat mendefinisikan relasi happened-before dinotasikan dengan 1048890 seperti

berikut

HB1 Jika ᴲ process pi e iersquo maka e ersquo

HB2 untuk setiap message m send(m) receive(m)

- Dimana send(m) adalah event dari pengiriman message dan receive(m) adalah event dari

penerimaan message

HB3 Jika e ersquo dan erdquo adalah event dimana e ersquo dan ersquo erdquo maka e erdquo

Relasi diilustrasikan pada gambar 5 Pada ketiga proses tersebut dapat dikombinasikan

menjadi a f Antar a dan e tidak ada relasi maka ditulis a e

31 Logical Clocks

Lamport menemukan sebuah mekanisme yang simple untuk mengurutkan happened-

before secara numeris Mekanisme ini disebut logical clock Lamport logical clock adalah

software counter yang bertambah secara monoton dimana nilainya tidak perlu menanggung

hubungan tertentu ke suatu physical clock Setiap proses pi tetap berada pada logical clock

masing-masing Timestamp dari suatu event e pada pi disini dinotasikan dengan Li(e) dan L(e)

Untuk notasi dalam suatu prose adalah sebagai berikut

LC 1 Li bertambah sebelum setiap event muncul pada proses pi Li = Li + 1

LC 2 (a) Ketika sebuah proses pi mengirim sebuah message m nilai L juga ditempelkan pada

nilai m t = Li

(b) pada saat menerima pesan (mt) sebuah proses pj menghitung L j = max(Lj t) dan lalu

mengaplikasikan LC1 sebelum melakukan timestamp untuk event receive(m)

32 Totally ordered logical clocks

Beberapa pasang event yang berbeda yang dihasilkan oleh proses yang berbeda telah

diidentifikasi dengan Lamport timestamp secara numeris Namun kita dapat menciptakan sebuah

urutan total peristiwa yaitu satu untuk yang semua pasangan dari event yang berbeda terjadi

Jika e adalah sebuah peristiwa yang terjadi di pi dengan local timestamp Ti dan e adalah sebuah

event yang terjadi di pj dengan local timestamp Tj kita mendefinisikan global logic timestamp

untuk event ini menjadi (Ti i) dan (Tj j) Dan kita define (Ti i) lt(Tj j) jika hanya jika salah Ti

ltTj atau Ti = Tj dan i ltj terpenuhi Urutan ini tidak memiliki arti fisik umum (karena

pengidentifikasi proses yang tidak beraturan) tetapi kadang-kadang berguna Lamport

menggunakannya misalnya untuk mengurutkan proses masuknya ke bagian kritis

33 Vector clocks

Mattern [1989] dan Fidge [1991] mengembangkan vector clocks untuk mengatasi

kekurangan pada Lamport clocks fakta bahwa dari L(e) lt L(ersquo) kita tidak dapat menyimpulkan

bahwa e ersquo Vektor clock untuk sebuah sistem dari N proses adalah sebuah array dari N

integer Setiap proses berada pada vektor clock Vi masing-masing Aturan adalah sebagai berikut

VC1 Inisialisasi Vi [j] = 0 for ij = 12hellip N

VC2 sesaat sebelum pi men-timestamp sebuah event diset Vi[i] = Vi[i] + 1

VC3 pi memasukan nilai t = Vi pada setiap message yang diirim

VC4 Ketika pi menarima sebuah timestamp t pada sebuah sebuah message pi di set Vi[j] =

max(Vi[j] t[j]) for j = 12hellipN

DAFTAR PUSTAKA

Herusetyo Arif Time and Global State UGM Publisher Yogyakarta

2006

L Lamport Time Clocks And The Ordering Of Events In A Distributed

System Computer Science Laboratory SRI International Massachusett

1990

Coulouris George Distributed System Concept and Design Addison

Press Wesley 2001

Dari sudut pandang dari setiap single proses event-event diurutkan berdasakan waktu

seperti pada local clock Tetapi seperti yang dikatakan oleh Lamport [1978] kita tidak dapat

melakukan singkronisasi clock secara sempurna pada sebuah sistem terdistribusi Kita tidak

dapat secara umum menggunakan physical time untuk menentukan urutan dari suatu event yang

terjadi Secara umum kita dapat menggunakan sebuah skema yang mirip dengan physical tapi

pada sistem terdistribusi digunakan untuk mengurutkan event-event yang terjadi pada proses

yang berbeda Pengurutan ini berdasarkan pada dua hal yang simple dan intuitif

Jika dua event terjadi bersamaam pada satu process yang sama pi (i = 12 hellip N) kemudian

event-event tersebut terjadi sesuai dengan urutan pi yang kita sebutkan diatas

Kapan saja sebuah message dikirim diantara proses-proses event dari pengiriman message

terjadi sebelum event dari penerimaan message

Lamport menyebutkan partial ordering diperoleh dengan men-generalalisasikan kedua hubungan

ini relasi happened-before Istilah ini biasa juga disebut causal ordering atau potential causal

ordering Kita dapat mendefinisikan relasi happened-before dinotasikan dengan 1048890 seperti

berikut

HB1 Jika ᴲ process pi e iersquo maka e ersquo

HB2 untuk setiap message m send(m) receive(m)

- Dimana send(m) adalah event dari pengiriman message dan receive(m) adalah event dari

penerimaan message

HB3 Jika e ersquo dan erdquo adalah event dimana e ersquo dan ersquo erdquo maka e erdquo

Relasi diilustrasikan pada gambar 5 Pada ketiga proses tersebut dapat dikombinasikan

menjadi a f Antar a dan e tidak ada relasi maka ditulis a e

31 Logical Clocks

Lamport menemukan sebuah mekanisme yang simple untuk mengurutkan happened-

before secara numeris Mekanisme ini disebut logical clock Lamport logical clock adalah

software counter yang bertambah secara monoton dimana nilainya tidak perlu menanggung

hubungan tertentu ke suatu physical clock Setiap proses pi tetap berada pada logical clock

masing-masing Timestamp dari suatu event e pada pi disini dinotasikan dengan Li(e) dan L(e)

Untuk notasi dalam suatu prose adalah sebagai berikut

LC 1 Li bertambah sebelum setiap event muncul pada proses pi Li = Li + 1

LC 2 (a) Ketika sebuah proses pi mengirim sebuah message m nilai L juga ditempelkan pada

nilai m t = Li

(b) pada saat menerima pesan (mt) sebuah proses pj menghitung L j = max(Lj t) dan lalu

mengaplikasikan LC1 sebelum melakukan timestamp untuk event receive(m)

32 Totally ordered logical clocks

Beberapa pasang event yang berbeda yang dihasilkan oleh proses yang berbeda telah

diidentifikasi dengan Lamport timestamp secara numeris Namun kita dapat menciptakan sebuah

urutan total peristiwa yaitu satu untuk yang semua pasangan dari event yang berbeda terjadi

Jika e adalah sebuah peristiwa yang terjadi di pi dengan local timestamp Ti dan e adalah sebuah

event yang terjadi di pj dengan local timestamp Tj kita mendefinisikan global logic timestamp

untuk event ini menjadi (Ti i) dan (Tj j) Dan kita define (Ti i) lt(Tj j) jika hanya jika salah Ti

ltTj atau Ti = Tj dan i ltj terpenuhi Urutan ini tidak memiliki arti fisik umum (karena

pengidentifikasi proses yang tidak beraturan) tetapi kadang-kadang berguna Lamport

menggunakannya misalnya untuk mengurutkan proses masuknya ke bagian kritis

33 Vector clocks

Mattern [1989] dan Fidge [1991] mengembangkan vector clocks untuk mengatasi

kekurangan pada Lamport clocks fakta bahwa dari L(e) lt L(ersquo) kita tidak dapat menyimpulkan

bahwa e ersquo Vektor clock untuk sebuah sistem dari N proses adalah sebuah array dari N

integer Setiap proses berada pada vektor clock Vi masing-masing Aturan adalah sebagai berikut

VC1 Inisialisasi Vi [j] = 0 for ij = 12hellip N

VC2 sesaat sebelum pi men-timestamp sebuah event diset Vi[i] = Vi[i] + 1

VC3 pi memasukan nilai t = Vi pada setiap message yang diirim

VC4 Ketika pi menarima sebuah timestamp t pada sebuah sebuah message pi di set Vi[j] =

max(Vi[j] t[j]) for j = 12hellipN

DAFTAR PUSTAKA

Herusetyo Arif Time and Global State UGM Publisher Yogyakarta

2006

L Lamport Time Clocks And The Ordering Of Events In A Distributed

System Computer Science Laboratory SRI International Massachusett

1990

Coulouris George Distributed System Concept and Design Addison

Press Wesley 2001

31 Logical Clocks

Lamport menemukan sebuah mekanisme yang simple untuk mengurutkan happened-

before secara numeris Mekanisme ini disebut logical clock Lamport logical clock adalah

software counter yang bertambah secara monoton dimana nilainya tidak perlu menanggung

hubungan tertentu ke suatu physical clock Setiap proses pi tetap berada pada logical clock

masing-masing Timestamp dari suatu event e pada pi disini dinotasikan dengan Li(e) dan L(e)

Untuk notasi dalam suatu prose adalah sebagai berikut

LC 1 Li bertambah sebelum setiap event muncul pada proses pi Li = Li + 1

LC 2 (a) Ketika sebuah proses pi mengirim sebuah message m nilai L juga ditempelkan pada

nilai m t = Li

(b) pada saat menerima pesan (mt) sebuah proses pj menghitung L j = max(Lj t) dan lalu

mengaplikasikan LC1 sebelum melakukan timestamp untuk event receive(m)

32 Totally ordered logical clocks

Beberapa pasang event yang berbeda yang dihasilkan oleh proses yang berbeda telah

diidentifikasi dengan Lamport timestamp secara numeris Namun kita dapat menciptakan sebuah

urutan total peristiwa yaitu satu untuk yang semua pasangan dari event yang berbeda terjadi

Jika e adalah sebuah peristiwa yang terjadi di pi dengan local timestamp Ti dan e adalah sebuah

event yang terjadi di pj dengan local timestamp Tj kita mendefinisikan global logic timestamp

untuk event ini menjadi (Ti i) dan (Tj j) Dan kita define (Ti i) lt(Tj j) jika hanya jika salah Ti

ltTj atau Ti = Tj dan i ltj terpenuhi Urutan ini tidak memiliki arti fisik umum (karena

pengidentifikasi proses yang tidak beraturan) tetapi kadang-kadang berguna Lamport

menggunakannya misalnya untuk mengurutkan proses masuknya ke bagian kritis

33 Vector clocks

Mattern [1989] dan Fidge [1991] mengembangkan vector clocks untuk mengatasi

kekurangan pada Lamport clocks fakta bahwa dari L(e) lt L(ersquo) kita tidak dapat menyimpulkan

bahwa e ersquo Vektor clock untuk sebuah sistem dari N proses adalah sebuah array dari N

integer Setiap proses berada pada vektor clock Vi masing-masing Aturan adalah sebagai berikut

VC1 Inisialisasi Vi [j] = 0 for ij = 12hellip N

VC2 sesaat sebelum pi men-timestamp sebuah event diset Vi[i] = Vi[i] + 1

VC3 pi memasukan nilai t = Vi pada setiap message yang diirim

VC4 Ketika pi menarima sebuah timestamp t pada sebuah sebuah message pi di set Vi[j] =

max(Vi[j] t[j]) for j = 12hellipN

DAFTAR PUSTAKA

Herusetyo Arif Time and Global State UGM Publisher Yogyakarta

2006

L Lamport Time Clocks And The Ordering Of Events In A Distributed

System Computer Science Laboratory SRI International Massachusett

1990

Coulouris George Distributed System Concept and Design Addison

Press Wesley 2001

32 Totally ordered logical clocks

Beberapa pasang event yang berbeda yang dihasilkan oleh proses yang berbeda telah

diidentifikasi dengan Lamport timestamp secara numeris Namun kita dapat menciptakan sebuah

urutan total peristiwa yaitu satu untuk yang semua pasangan dari event yang berbeda terjadi

Jika e adalah sebuah peristiwa yang terjadi di pi dengan local timestamp Ti dan e adalah sebuah

event yang terjadi di pj dengan local timestamp Tj kita mendefinisikan global logic timestamp

untuk event ini menjadi (Ti i) dan (Tj j) Dan kita define (Ti i) lt(Tj j) jika hanya jika salah Ti

ltTj atau Ti = Tj dan i ltj terpenuhi Urutan ini tidak memiliki arti fisik umum (karena

pengidentifikasi proses yang tidak beraturan) tetapi kadang-kadang berguna Lamport

menggunakannya misalnya untuk mengurutkan proses masuknya ke bagian kritis

33 Vector clocks

Mattern [1989] dan Fidge [1991] mengembangkan vector clocks untuk mengatasi

kekurangan pada Lamport clocks fakta bahwa dari L(e) lt L(ersquo) kita tidak dapat menyimpulkan

bahwa e ersquo Vektor clock untuk sebuah sistem dari N proses adalah sebuah array dari N

integer Setiap proses berada pada vektor clock Vi masing-masing Aturan adalah sebagai berikut

VC1 Inisialisasi Vi [j] = 0 for ij = 12hellip N

VC2 sesaat sebelum pi men-timestamp sebuah event diset Vi[i] = Vi[i] + 1

VC3 pi memasukan nilai t = Vi pada setiap message yang diirim

VC4 Ketika pi menarima sebuah timestamp t pada sebuah sebuah message pi di set Vi[j] =

max(Vi[j] t[j]) for j = 12hellipN

DAFTAR PUSTAKA

Herusetyo Arif Time and Global State UGM Publisher Yogyakarta

2006

L Lamport Time Clocks And The Ordering Of Events In A Distributed

System Computer Science Laboratory SRI International Massachusett

1990

Coulouris George Distributed System Concept and Design Addison

Press Wesley 2001

DAFTAR PUSTAKA

Herusetyo Arif Time and Global State UGM Publisher Yogyakarta

2006

L Lamport Time Clocks And The Ordering Of Events In A Distributed

System Computer Science Laboratory SRI International Massachusett

1990

Coulouris George Distributed System Concept and Design Addison

Press Wesley 2001