Month: January 2015

Lamport timestamps adalah algoritma sederhana yang digunakan untuk menentukan urutan kejadian pada sistem komputer terdistribusi. Algoritma ini digunakan untuk menyediakan permintaan event parsial dengan overhead yang minimal, dan konseptual memberikan titik awal untuk metode jam vektor yang lebih maju, sebagain node atau proses yang berbeda biasanya tidak akan tersinkron dengan sempurna.

Algoritma terdistribusi seperti sinkronisasi sumber daya sering bergantung pada beberapa metode nebgurutkan events ke fungsi. Sebagai contoh, anggap sistem dengan dua proses dan disk. Proses mengirim pesan satu sama lain, dan juga mengirim pesan ke disk untuk meminta akses. Disk mengizinkan akses dalam urutan pesan yang dikirim. Sekarang, bayangkan proses 1 mengirimkan pesan ke disk meminta akses untuk menulis, dan kemudian mengirimkan pesan ke proses 2 meminta untuk membaca. Proses 2 menerima pesan, dan sebagai hasilnya mengirim pesan sendiri ke disk. Sekarang, karena beberapa penundaan waktu, disk menerima kedua pesan pada saat yang sama: bagaimana cara menentukan pesan terjadi-sebelum yang lain? (A terjadi sebelum B-jika salah satu bisa berpndah dari A ke B dengan angkah sequences dari dua jenis: bergerak maju sambil tetap dalam proses yang sama, dan mengikuti pesan dari yang mengirim ke penerimaan.) Algoritma jam logis menyediakan mekanisme untuk menentukan fakta tentang urutan kejadian tersebut.

Lamport menciptakan mekanisme yang sederhana dimana terjadi-sebelum pemesanan dapat ditangkap secara numerik. Sebuah jam logis Lamport adalah counter software incrementing yang dipertahankan dalam setiap proses.

Ini mengikuti beberapa aturan sederhana:

• Sebuah proses mengincrement counternya sebelum setiap peristiwa dalam proses tersebut;

• Ketika proses mengirim pesan, itu termasuk nilai counter dengan pesan;

• Pada saat menerima pesan, proses penerima set counter menjadi lebih besar dari maksimum nilainya sendiri dan nilai yang diterima sebelum mempertimbangkan pesan yang diterima.

Secara konseptual, jam logis ini dapat dianggap sebagai sebuah jam yang hanya memiliki makna dalam kaitannya dengan pesan bergerak antara proses. Ketika proses menerima pesan, itu resynchronizes jam logis dengan pengirim itu.

Pertimbangan

Untuk setiap dua peristiwa yang berbeda a dan b yang terjadi dalam proses yang sama, dan C (x) menjadi timestamp untuk acara x tertentu, perlu bahwa C (a) tidak pernah sama C (b).

Oleh karena itu perlu bahwa:

• Jam logis diatur sehingga ada minimal satu jam “tik” (kenaikan counter) antara peristiwa a dan b;

• Dalam lingkungan multiprocess atau multithreaded, mungkin perlu untuk melampirkan ID proses (PID) atau ID unik lainnya untuk penanda sehingga dimungkinkan untuk membedakan antara peristiwa a dan b yang mungkin terjadi secara bersamaan dalam proses yang berbeda.

Implikasi

Jam Lamport dapat digunakan untuk membuat pengurutan kausal sebagian dari events antara proses. Mengingat jam logis berikut aturan-aturan ini, hubungan berikut ini benar: jika a -> b maka C (a) <C (b), di mana ->, berarti terjadi-sebelumnya.

Hubungan ini hanya berjalan satu arah, dan disebut kondisi konsistensi jam: jika salah satu event datang sebelum yang lain, maka jam logis bahwa acara datang sebelum yang lain. Kondisi Jam konsistensi yang kuat, yang dua arah (jika C (a) <C (b) maka -> b), dapat diperoleh dengan teknik lain seperti jam vektor. Hanya menggunakan jam Lamport sederhana, hanya kausal pemesanan parsial dapat disimpulkan dari jam.

Namun, melalui kontrapositif tersebut, memang benar bahwa C (a) \ nless C (b) menyiratkan -> b. Jadi, misalnya, jika C (a) \ GEQ C (b) maka tidak bisa terjadi sebelum-b. Cara lain untuk menempatkan ini adalah bahwa C (a) <C (b) berarti bahwa mungkin telah terjadi sebelum-b, atau menjadi tak tertandingi dengan b dalam terjadi-sebelum memesan, tapi tidak terjadi setelah b.

Namun demikian, Lamport cap waktu dapat digunakan untuk membuat pemesanan total kejadian dalam sistem terdistribusi dengan menggunakan beberapa mekanisme sewenang-wenang memutuskan hubungan (misalnya ID proses). Peringatan adalah bahwa pemesanan ini artifactual dan tidak dapat diandalkan untuk menyiratkan hubungan sebab akibat.

Jam Logis Lamport dalam Sistem Terdistribusi

• Dalam sistem terdistribusi, tidak mungkin dalam praktek untuk sinkronisasi waktu di entitas (biasanya dianggap sebagai proses) dalam sistem; karenanya, entitas dapat menggunakan konsep jam logis berdasarkan peristiwa di mana mereka berkomunikasi.

• Jika dua entitas tidak bertukar pesan, maka mereka mungkin tidak perlu berbagi jam yang sama; peristiwa yang terjadi pada entitas-entitas tersebut disebut sebagai peristiwa bersamaan.

• Di antara proses pada mesin lokal yang sama kita bisa memesan peristiwa berdasarkan pada jam lokal dari sistem.

• Ketika dua entitas berkomunikasi melalui pesan lewat, maka acara kirim dikatakan ‘terjadi sebelum’ menerima acara, dan urutan logis dapat dibentuk antara peristiwa.

• Sebuah sistem terdistribusi dikatakan memiliki urutan parsial jika kita dapat memiliki hubungan urutan parsial antara peristiwa dalam sistem. Jika ‘totalitas’, yaitu, hubungan kausal antara semua kejadian dalam sistem, dapat dibentuk, maka sistem dikatakan memiliki total order.

• Sebuah entitas tunggal tidak dapat memiliki dua peristiwa terjadi secara bersamaan. Jika sistem memiliki total order kita dapat menentukan urutan di antara semua peristiwa dalam sistem. Jika sistem memiliki urutan parsial antara proses,  jenis yang disediakan oleh type urutan Lampor jam logist, maka kita hanya bisa mengatakan pengurutan antara entitas yang berinteraksi. Lamport ditujukan memesan dua peristiwa dengan timestamp yang sama (atau counter): “Untuk memecahkan ikatan, kita menggunakan jumlah pemesanan sewenang-wenang.” Dengan demikian dua cap waktu atau counter mungkin sama dalam suatu sistem terdistribusi, tetapi dalam menerapkan logis peristiwa algoritma jam yang terjadi akan selalu menjaga setidaknya memesan parsial yang ketat.

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 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.

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).

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 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 Vimasing-masing.

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.