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 = 1,2, … ,N), kemudian eventevent 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.

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 (m,t), sebuah proses pj menghitung L j:= max(Lj,t) dan lalumengaplikasikan LC1 sebelum melakukan timestamp untuk event receive(m).

Lamport Timestamps

Berfungsi untuk mensinkronkan jam logis a → b dibaca “ a terjadi sebelum b” yang berarti semua  proses menyetujui bahwa kejadian pertama yang akan terjadi baru kemudian kejadian kedua.

Ada dua situasi dimana peristiwan terjadi sebelum hubungan dapat diamati secara langsung :

1. Apabila a dan b merupakan peristiwa dalam satu proses dan a terjadi sebelum b , maka → b adalah benar
2. Apabila a merupakan peristiwa pesan yang dikirim oleh salah satu proses dan b merupakan acara dari pesan yang diterima oleh proses lain,maka → b adalah benar.Pesan tidak dapat diterima bila belum dikirim atau dapat juga terjadi di waktu yang sama waktu pengiriman karena membutuhkan waktu terbatas jumlah nol waktu untuk tiba.

Yang dibutuhkan dalam mengukur waktu hingga tiap acara,dapat menetapkan dalam nilai waktu C(a) dimana semua proses setuju. Nilai-nilai waktu wajib mempunyai property bahwa apabila → b, maka C(a) < (b). Pengulangan kondisi yang dinyatakan sebelumnya, apabila a dan b merupakan dua peristiwa dalam satu proses dan terjadi sebelum b , maka C(a) < C(b) . Sehingga dalam proses pengiriman pesan dengan salah satu proses dan b merupakan penerima pesan dengan proses lainnya, maka C(a) dan C(b) wajib ditentukan agar semua proses setuju dengan nilai C(a) dan C(b) dengan C(a) < C(b) . Tidak hanya itu, waktu jam ( yaitu C ) dibuat selalu maju ( naik ) dan tidak pernah mundur ( turun ). Dengan begitu koreksi waktu dapat dibuat dengan menambahkan nilai positif, tidak pernah dengan mengurangkan satu.

Totally Oredered 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 pidengan 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) <(Tj, j) jika hanya jika salah Ti <Tj atau Ti = Tj dan i <j 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.

Vector Clocks

Mattern [1989] dan Fidge [1991] mengembangkan vector clocks untuk mengatasi kekurangan pada Lamport clocks : fakta bahwa dari L(e) < L(e’) kita tidak dapat menyimpulkan bahwa e → e’ . Vektor clock untuk sebuah sistem dari N proses adalah sebuah array dari N integer. Setiap proses berada pada vektor clock Vi masing-masing. Aturannya adalah sebagai berikut :

VC1 : Inisialisasi Vi[j] = 0 for i,j = 1,2,… , N
VC2 : sesaat sebelum pi men-timestamp sebuah event, diset Vi[i] := Vi[i] + 1
VC3 : pimemasukan nilai t = Vipada setiap message yang diirim
VC4 : Ketika pi menarima sebuah timestamp tpada sebuah sebuah message, pidi set Vi[j] :=
max(Vi[j], t[j]) , for j = 1,2,…,N.

Referensi :

• 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.
• https://www.scribd.com/doc/46593826/Logical-Clock-and-Synchronization
• http://esetblog.blogspot.com/2014/01/pertemuan-vii-sistem-terdistribusi.html