PERTEMUAN VII (SISTEM TERDISTRIBUSI)

SISTEM TERDISTRIBUSI

Chapter 5. Sinkronisasi

1 Sinkronisasi Clock

Sistem tersebar sebenarnya adalah proses-proses yang berkolaborasi atau bekerjasama. Sebelumya telah dibahas komunikasi yang merupakan dasar kesemuanya, dibahas juga penamaan yang penting untuk sumber daya berbagi, dan sekarang akan dibahas issue sinkronisasi. Sikronisasi sendiri diperlukan baik di sistem tunggal atau sistem tersebar dengan alasan yang sama.

Sikronisasi merupakan bagian penting untuk kerjasama  dalam :

• Pemakaian sumberdaya berbagi (Sharing resources)
• Pengurutan kejadian
• Kesepakatan clock tersebar

Gambar ini menggambarkan bahwa bila waktu pada output.o adalah 2144, kemudian source codenya dimodifikasi di komputer lain yang clocknya lebih lambat, sehingga waktu source code adalah 2143. Karena source code memiliki waktu yang lebih lama daripada file objeknya, maka make tidak akan melakukan rekompilasi.

Algoritma untuk sinkronisasi dalam sistem tersebar memiliki beberapa sifat:

• Informasi yang relevan tersebar di beberapa komputer
• Keputusan pembuatan proses hanya berdasarkan informasi local
• Peristiwa kegagalan dengan penyebab tunggal di dalam sistem harus dihindarkan
• Tidak tersedianya clock atau sumber waktu global yang akurat.

5.1.1 Clock fisik

Pada beberapa sistem, waktu clock aktual menjadi penting, contohnya real-time sistem. Untuk sistem ini diperlukan clock fisik eksternal. Karena alasan efisiensi dan redundansi, clock fisik jamak biasanya digunakan, yang mengakibatkan ada dua masalah muncul: 

• Bagaimana mensinkronkan eksternal clock tersebut dengan clock sebenarnya
• Bagaimana mensinkronkan antar clock yang ada.

Sebelum membahas jawaban masalah di atas, terlebih dahulu dilihat bagaimana pengukuran waktu aktual dilakukan. Saat dimana matahari mencapai titik tertinggi di langit disebut transit of the sun, dan terjadi di siang hari. Interval antar dua transit berturutan disebut solar day. Sedangkan solar second didefinisikan tepat 1/86400 dari solar day. International Atomic Time (disingkat IAT) adalah rata-rata jumlah tick dari jam atom cesium 133 sejak tanggal 1 januari 1958 dibagi 9.192.631.770.

Disebabkan waktu siang bertambah lama, TAI menjadi lebih lambat dibanding solar second. Untuk mengkoreksinya, digunakan leap second dengan cara meloncati waktu TAI sehingga sama dengan solar second (lihat gambar). Waktu yang telah dikoreksi ini disebut Universal Coordinated Time (UTC). NIST memiliki beberapa stasiun radio gelombang pendek yang memancarkan pulsa pada setiap awal detik UTC,yang dapat digunakan untuk sinkronisasi. Stasiun ini dikenal dengan nama WWV.

5.1.2 Algoritma Sinkronisasi Clock

Frekuensi detik clock logika tergantung dari nilai yang dimuat ke counter. Nilai ini yang menentukan resolusi clock. Interval waktu yang lebih kecil dari resolusi tidak dapat dibedakan. Laju pergeseran clock adalah perubahan offset antara clock dengan nominal referensi ideal per unit waktu yang diukur di referensi. Clock hardware hanya berupa nilai di dalam register, seperti nilai 32 bit, yang kelak di roll-over. Penanganan dilakukan dengan mengubah konstanta yang ditambahkan untuk memperoleh clock software yang biasanya berkisar di orde mikrodetik atau milidetik dari tanggal yang disepakati.

Algoritma Cristian

Bila sebuah mesin memiliki penerima WWV sehingga dapat berfungsi sebagai time server. Secara periodik, setiap mesin mengirim pesan ke time server menanyakan waktu terkini, Cutc. Ada 2 masalah dalam algo ini, masalah major dan minor. Masalah majornya adalah waktu penanya tidak boleh dimundurkan dan untuk mengatasinya adalah dengan memperlambat clock tick.

Masalah minor adalah waktu tunda dari balasan server,yang besarnya variatif tergantung beban jaringan. Diatasi dengan menghitung interval waktu pengiriman dan penerimaan pesan To sd T1 dan waktu penangan interupsi I, sehingga bisa dihitung lama propagasi pesan dalam satu arah(T1-T0-I)/2. Nilai ini dijadikan koreksi terhadap nilai waktu yang diperoleh.

Algoritma Berkeley

Algoritma Berkeley digunakan untuk mensinkronkan clock relatif terhadap clock lainnya, dan bukan terhadap master clock tertentu. Daemon di server time melakukan polling ke semua client, yang akan dijawab oleh setiap clock. Kemudian time daemon akan mengirim penyesuaiannya.

• Forward dapat dilakukan dengan meloncat
• Backward perlu perlambatan yang bertahap

1. Daemon time menanyakan nilai clock ke semua mesin
2. Mesin-mesin menjawab
3. Daemon time memberitahu semua mesin, berapa nilai koreksi yang harus digunakan.

Algoritma Rata-rata

Berbeda dengan metode sebelumnya yang terpusat, maka metode ini mensinkronkan clock dengan cara desentralisasi. Cara kerjanya dengan membagi waktu ke dalam interval  resinkronisasi yang lebarnya tetap. Interval ke I dimulai pada T0 + iR dan berjalan sampai T0+(I+1)R, dimana T0 adalah kesepakatan lalu dan R adalah parameter sistem. Pada setiap awal interval, setiap mesin mengumumkan waktu terkininya. Karena clock di mesin yang berbeda akan berjalan dengan laju yang berbeda pula, pengumuman ini tidak akan terjadi bersamaan. Sesudah mesin mengumumkan waktunya, timer lokal diaktifkan untuk mengumpulkan semua pengumuman yang diterima dalam interval S. Setelah semua pengumuman diterima, waktu yang baru dapat dihitung dengan algoritma yang ada. Algoritma paling sederhana adalah merata-ratakan nilai yang diperoleh dari semua mesin.

Sumber Clock Eksternal Jamak

Algoritma ini menjadi dasar untuk protokol NTP (Network Time Protocol). Interval waktu dapat ditentukan dengan menggunakan algoritma Cristian dengan waktu tunda perambatan yang diketahui.

Digunakan dalam sistem yang disinkronkan dengan sangat akurat.

Gambar 5.6 Sumber Clock Eksternal Jamak

• Waktu diperoleh dari beberapa sumber UTC
• Koreksi dari waktu rambat diperhitungkan
• Gunakan media overlap sebagai perkiraan terbaik

Standar waktu yang diterima bersumber pada satu set jam atom-jam atom. Bila perambatan sinyal radio tidak dipengaruhi oleh kondisi atmosfir, maka pemancaran sinyal waktu dan penerimaan sinyal tersebut dengan akurat dapat terjadi. Keakurasian terbaik yang dapat dicapai melalui satelit GEOS atau GPS berkisar 1.1 milidetik. Untuk aplikasi tertentu, didefinisikan kebenaran (correctness) sebagai dalam toleransi ∆ misal dalam 5 milidetik UTC. Definisi lain yang kadang-kadang digunakan adalah  t` > t => C(t`) > C(t).

5.1.3 Penggunaan Clock Sinkronisasi

Pelaksanaan sinkronisasi clock dalam skala luas terjadi baru-baru ini saja, yang salah satu teknologi enabling-nya adalah internet.  Yang dapat mensinkronkan jutaan clock dalam orde milidetik dengan UTC. Berbagai algoritma baru yang menggunakan clock sinkron mulai bermunculan, berikut ini contohnya

At-Most-Once Message Delivery

Setiap pesan membawa pengenal koneksi dan time stamp. Untuk setiap koneksi, server menyimpan time stamp terbaru ke dalam tabel. Bila ada pesan masuk dengan timestamp yang lebih lama daripada time stamp yang disimpan, maka pesan tersebut akan ditolak dan dianggap sebagai duplikat. Server menyimpan variabel global yang memungkinkannya untuk menghapus timestamp lama.

Konsistensi Cache Berbasis Clock

Konsistensi cache dalam file System tersebar menjadi perhatian karena setiap client menginginkan cache file di lokal komputer. Bila dua komputer memodifikasi file secara bersamaan, berpotensi menyebabkan inkonsistensi. Ide dasarnya bila client menginginkan sebuah file, lease akan diberikan untukmenentukan berapa lama copy tersebut valid. Bila lease sudah hampir habis berlakunya, client dapat meminta untuk memperbaharuinya. Bila lease habis berlakunya, cache dari copy tersebut tidak akan digunakan.

Propagasi lokal dalam proses P dapat dilakukan sebagai berikut. Awalnya, semua proxy di P ditandai tidak ada. Para kolektor lokal mulai menelusuri mulai penelusuran dari set yang terdiri dari kerangka yang sebelumnya telah ditandai keras, serta dari benda-benda di set root. Tanda Hard disebarkan ke semua objek (yaitu, objek lokal dan proxy) yang dicapai dari set ini. Sebuah jejak kedua dilakukan dari kerangka yang telah ditandai lembut. Jika proxy yang kini mencapai yang ditandai tidak ada, tandanya berubah menjadi lembut. Jika proxy ditandai keras, tetap ditandai seperti. Akibatnya, setelah propagasi lokal, masing-masing proxy di proses akan ditandai baik tidak ada, lembut, atau keras. Gambar. 4-34 (a).

            Langkah ketiga terdiri dari menyebarkan tanda dari proxy untuk kerangka mereka terkait. Dengan kata lain, tanda yang disebarkan antara proses yang berbeda. Secara khusus, jika proxy telah ditandai keras, pesan harus dikirim ke kerangka yang terkait untuk menandai sulit juga, jika tidak sudah ditandai seperti. Sebuah pesan akan dikirim hanya jika kerangka terletak di dalam kelompok. Tanda lembut tidak harus disebarkan: fase menandai awal sudah ditetapkan bahwa setiap kerangka dalam kelompok ditandai baik lembut atau keras.

            Hasil Langkah keempat dari propagasi global marka keras pada langkah sebelumnya. Sebuah kerangka dalam, katakanlah, P proses sekarang mungkin memiliki tandanya berubah dari lembut ke keras. Perubahan ini berasal dari fakta bahwa kerangka ternyata dicapai dari obyek yang terkandung dalam set akar dari proses remote. Akibatnya, ini tanda keras pertama perlu disebarkan ke proxy lokal di P, dan kemudian, secara global disebarkan kepada proses tetangga. Dengan kata lain, langkah 2 dan 3 harus diulang asalkan tanda dapat baik secara lokal atau global disebarkan. Segera setelah stabilisasi telah tercapai, yaitu, tidak ada perubahan yang lebih berkenaan dengan menandai terjadi proses dalam kelompok, hasil algoritma dengan langkah berikutnya. Dalam contoh kita, efek mengulangi langkah 2 dan 3 mengarah ke final menandai seperti ditunjukkan pada Gambar. 4-34 (c).

            Langkah kelima dan terakhir terdiri dari menghilangkan benda terjangkau, termasuk proxy terjangkau, serta mereka proxy dan tengkorak yang sudah ditandai lembut. Penting untuk dicatat bahwa yang terakhir tidak dapat diraih dari luar kelompok, mereka juga tidak dapat dicapai dari objek dalam satu set root. Dengan kata lain, soft-ditandai proxy dan kerangka hanya mengacu pada satu sama lain, dan dengan demikian harus dihapus.

            Sampah reklamasi dapat dilakukan sebagai efek samping dari propagasi lokal. Alih-alih eksplisit menghapus entitas dalam langkah terakhir, kerangka ditandai lembut diubah untuk merujuk nihil. Akibatnya, dapat direklamasi kemudian ketika pengumpulan sampah lokal dijalankan lagi. Selain itu, jika objek yang terkait dengan kerangka yang sekarang menjadi terjangkau, maka akan direklamasi juga. Jika proxy lokal disebut dengan objek yang juga tidak lagi terjangkau, mereka akan ditandai dan tetap tidak ditandai seperti itu. Oleh karena itu aman untuk membiarkan pengumpul sampah lokal merebut kembali proxy none-ditandai, setelah mengirim pesan ke penurunan kerangka proxy terkait di salah satu proses remote.

            Dengan hirarki mengorganisir ke dalam kelompok, solusi yang lebih scalable untuk pengumpulan sampah terdistribusi dapat dicapai. Ide dasarnya adalah untuk membiarkan tingkat rendah kelompok mengumpulkan sampah, dan meninggalkan analisis referensi antarkelompok kepada kelompok yang lebih tinggi-tingkat berikutnya. Dengan membiarkan rendah tingkat kelompok mengurangi jumlah objek yang perlu ditelusuri, lebih tinggi tingkat kelompok dasarnya beroperasi pada jumlah yang sama sebagai obyek masing-masing jika subkelompok, tetapi yang tersebar di jaringan yang lebih besar. Kami menghilangkan detail, yang dapat ditemukan dalam (Lang et al, 1992.).

Beberapa Sumber Waktu Eksternal

Untuk sistem di mana sinkronisasi yang sangat akurat dengan UTC diperlukan, adalah mungkin untuk equib sistem dengan beberapa receiver untuk WWV, GEOS, atau lainnya UTC sumber. Namun, karena ketidaktelitian melekat dalam sumber waktu sendiri serta fluktuasi jalur sinyal, yang terbaik sistem operasi dapat Anda lakukan adalah untuk membentuk rentang (interval waktu) di mana UTC jatuh. Secara umum, sumber berbagai waktu akan menghasilkan rentang yang berbeda, yang dengan demikian mensyaratkan bahwa mesin yang menyertainya datang kesebuah kesepakatan umum.

Untuk mencapai kesepakatan ini, setiap prosesor dengan sumber UTC bisa menyiarkan jangkauan berkala, untuk istance, pada awal tepat dari setiap menit UTC. Tak satu pun dari prosesor akan mendapatkan paket waktu seketika. Parahnya lagi, penundaan antara transmisi dan penerimaan tergantung pada jarak kabel dan jumlah router bahwa paket harus melintasi, yang berbeda untuk setiap pasangan (UTC sumber, prosesor). Faktor-faktor lain dan juga memainkan peran, seperti keterlambatan akibat tabrakan ketika beberapa mesin mencoba untuk mengirimkan pada Ethernet pada saat yang sama. Selain itu, jika prosesor sedang sibuk menangani paket sebelumnya, tidak mungkin bahkan melihat paket waktu untuk sejumlah besar milidetik, memperkenalkan ketidakpastian tambahan ke waktu.

5.1.3 Penggunaan Jam Synchronized

Dalam beberapa tahun terakhir, perangkat keras dan perangkat lunak yang diperlukan untuk sinkronisasi jam pada skala luas (misalnya, melalui internet seluruh) telah menjadi mudah tersedia. Dengan teknologi baru ini, adalah mungkin untuk menjaga jutaan jam disinkronisasi ke dalam beberapa milidetik UTC. Algoritma baru yang memanfaatkan jam disinkronkan baru mulai muncul. Salah satu contoh, dibahas dalam (Liskov, 1993), menyangkut bagaimana menegakkan pada pengiriman pesan yang paling sekali untuk aserver, bahkan dalam menghadapi crash. Pendekatan tradisional untuk setiap pesan menanggung nomor pesan yang unik, dan memiliki setiap toko server semua jumlah pesan yang telah melihat sehingga dapat mendeteksi pesan baru dari transmisi ulang. Masalah dengan algoritma ini adalah bahwa jika crash server dan reboot, ia kehilangan tabel nomor pesan. Juga untuk berapa lama harus nomor pesan disimpan? Menggunakan waktu, algoritma dapat dimodifikasi sebagai berikut. Sekarang, setiap pesan membawa connection identifier (dipilih oleh pengirim) dan timestamp. Untuk setiap koneksi, server mencatat dalam sebuah tabel timestamp terbaru itu telah melihat. Jika ada pesan yang masuk untuk koneksi lebih rendah dari timestamp disimpan untuk koneksi itu, pesan akan ditolak sebagai duplikat. Untuk memungkinkan untuk menghapus cap waktu lama, setiap server terus mempertahankan variabel global.

G = CurrentTime - MaxLifeTime – MaxClockSkew

Yang MaxClockSkew adalah waktu maksimum pesan dapat hidup dan MaxClockSkew adalah seberapa jauh dari UTC jam yang mungkin paling buruk. Setiap timestamp tua dari G aman dapat dihapus dari tabel karena semua pesan yang sudah lama mati. Jika pesan masuk memiliki pengenal koneksi yang tidak diketahui, itu diterima jika timestamp yang lebih baru daripada G dan ditolak jika timestamp adalah lebih tua dari G karena apa pun yang tua pasti merupakan duplikat. Akibatnya, G adalah ringkasan dari nomor pesan dari semua pesan lama. AT Setiap waktu saat ditulis ke disk.

Ketika server crash dan kemudian reboot, itu ulang G dari waktu yang disimpan pada disk dan bertahap dengan periode update, AT. Setiap pesan yang masuk dengan timestamp tua dari G ditolak sebagai duplikat. Sebagai konsekuensinya, setiap pesan yang mungkin telah diterima sebelum kecelakaan tersebut ditolak. Beberapa pesan baru mungkin salah ditolak, tetapi di bawah semua kondisi algoritma mempertahankan di-paling-sekali semantik. Selain algoritma ini, Liskov (1993) juga menjelaskan bagaimana jam disinkronisasi dapat digunakan untuk mencapai konsistensi cache, bagaimana menggunakan time-out tiket di otentikasi sistem terdistribusi, dan bagaimana menangani komitmen dalam transaksi atom. Kita akan membahas beberapa algoritma dalam bagian berikutnya. Sebagai sinkronisasi waktu meningkatkan, aplikasi tidak diragukan lagi baru untuk itu akan ditemukan.

5.2 LOGIS Jam

Untuk berbagai tujuan, itu sudah cukup bahwa semua mesin setuju pada waktu yang sama. Hal ini tidak penting bahwa saat ini juga setuju dengan real time seperti yang diumumkan di radio setiap jam. Untuk menjalankan make, misalnya, adalah cukup bahwa semua mesin setuju bahwa itu adalah 10:00, bahkan jika itu benar-benar 10:02. Jadi untuk kelas tertentu dari algoritma, itu adalah konsistensi internal dari jam yang penting, bukan apakah mereka sangat dekat dengan real time. Untuk algoritma ini, itu adalah konvensional untuk berbicara dari jam sebagai jam logis.

Dalam sebuah makalah klasik, Lamport (1978) menunjukkan bahwa meskipun sinkronisasi jam adalah mungkin, maka tidak perlu mutlak. Jika dua proses tidak berinteraksi, tidak perlu bahwa jam mereka akan disinkronkan karena kurangnya sinkronisasi tidak akan diamati dan dengan demikian tidak dapat menimbulkan masalah. Selain itu, dia menunjukkan bahwa apa yang biasanya penting bukanlah bahwa semua proses setuju pada apa waktu itu, melainkan bahwa mereka setuju pada urutan di mana peristiwa terjadi. Dalam contoh make diberikan dalam bagian sebelumnya, yang terpenting adalah apakah input.c lebih tua atau lebih baru dari masukan.0, bukan kali mutlak mereka penciptaan.

Pada bagian ini kita akan membahas algoritma Lampotr, yang mensinkronisasikan jam logis. Juga, kita dicuss perpanjangan pendekatan Lamport yang disebut cap waktu vektor. Lamport diperpanjang karyanya sendiri (Lamport, 1990).

5.2.1 Lamport Timestamps

Untuk menyinkronkan jam logis, Lamport mendefinisikan hubungan yang disebut terjadi sebelumnya. Ekspresi a → b dibaca "a terjadi sebelum b" dan berarti bahwa semua proses setuju bahwa peristiwa pertama terjadi, maka setelah itu, acara b terjadi. Terjadi sebelum hubungan dapat diamati secara langsung dalam dua situasi:

1.    Jika a dan b adalah peristiwa dalam proses yang sama, dan terjadi sebelum b, maka →   b benar.

2.    Jika adalah peristiwa pesan yang dikirim oleh salah satu proses, dan b adalah acara dari pesan yang diterima oleh proses lain, maka → b juga benar pesan tidak dapat diterima sebelum dikirim, atau bahkan pada saat yang sama waktu pengiriman, karena dibutuhkan terbatas, jumlah nol waktu untuk tiba.

Terjadi sebelumnya merupakan relasi transitif, jadi jika → b dan b → c, maka → c. Jika dua peristiwa, x dan y, terjadi dalam proses yang berbeda yang tidak bertukar pesan (bahkan secara tidak langsung melalui pihak ketiga), maka x → y tidak benar, tetapi juga tidak ada y → x. Peristiwa ini dikatakan bersamaan, yang berarti thet ada van dikatakan (atau perlu dikatakan) tentang kapan peristiwa itu terjadi pertama.

Apa yang kita butuhkan adalah cara mengukur waktu sehingga untuk setiap acara,, kita dapat menetapkan dalam nilai waktu C (a) di mana semua proses setuju. Nilai-nilai waktu harus memiliki properti bahwa jika → b, maka C (a) <(b). Untuk ulangi kondisi yang kita dinyatakan sebelumnya, jika a dan b adalah dua peristiwa dalam proses yang sama dan terjadi sebelum b, maka C (a) <C (b). Demikian pula, jika adalah pengiriman pesan oleh salah satu proses dan b adalah penerimaan pesan bahwa dengan proses lain, maka C (a) dan C (b) harus ditentukan sedemikian rupa sehingga eveyone setuju pada nilai-nilai C (a) dan C (b) dengan C (a) <C (b). Selain itu, waktu jam, C, harus selalu maju (meningkat), tidak pernah mundur (menurun). Koreksi waktu dapat dibuat dengan menambahkan nilai positif, tidak pernah dengan mengurangkan satu.

Sekarang mari kita lihat algoritma Lamport diusulkan untuk menugaskan kali untuk evevts. Perhatikan tiga proses yang digambarkan dalam gambar. 5-7 (a). Proses berjalan pada mesin yang berbeda, masing-masing dengan jam sendiri, berjalan dengan kecepatan sendiri. Seperti dapat dilihat dari gambar, ketika jam telah berlalu 6 kali dalam proses 0, telah dicentang 8 kali dalam proses 1 dan 0 kali dalam proses 2. Setiap jam berjalan dengan laju yang konstan, tapi harga berbeda karena perbedaan dalam kristal.

Pada waktu 6, proses 0 mengirimkan pesan untuk memproses 1. Berapa lama pesan ini diperlukan untuk tiba tergantung pada jam whhose Anda percaya. Dalam hal apapun, jam dalam proses 1 berbunyi 16 ketika tiba. Jika pesan membawa waktu mulai, 6, di dalamnya, proses 1 akan menyimpulkan bahwa butuh 10 kutu untuk melakukan perjalanan. Nilai ini tentu mungkin. Menurut penalaran ini, pesan B 1 ke 2 membutuhkan 16 kutu, lagi nilai yang masuk akal.

Sekarang tiba bagian menyenangkan. Pesan C 2-1 daun pada 60 dan tiba di 56. Demikian pula, pesan D 1-0 daun pada 64 dan tiba di 54. Nilai-nilai ini jelas tidak mungkin. Ini adalah situasi ini yang harus dicegah. Solusi Lamport ini mengikuti langsung dari terjadi-sebelum hubungan. Karena C kiri di 60, itu harus tiba di 61 atau yang lebih baru. Oleh karena itu, setiap pesan membawa waktu pengiriman sesuai dengan jam pengirim. Ketika pesan tiba dan jam penerima menunjukkan nilai sebelum waktu pesan itu dikirim, penerima cepat maju jam untuk menjadi salah satu lebih dari waktu pengiriman. Dalam ara. 5-7 (b) kita melihat bahwa C sekarang tiba di 61. Demikian pula, D tiba di 70. Dengan satu tambahan kecil, algoritma ini memenuhi persyaratan kami untuk waktu global. Selain itu adalah bahwa antara Avery dua peristiwa, jam harus centang setidaknya sekali. Jika proses mengirim atau menerima dua pesan secara berurutan, sekali harus memajukan clock oleh(setidaknya) satu tik diantara mereka.

Dalam beberapa situasi, persyaratan tambahan yang diinginkan, tidak ada dua peristiwa yang pernah terjadi pada waktu yang tepat sama. Untuk mencapai tujuan ini, kita dapat melampirkan jumlah proses di mana acara occures dengan urutan rendah dan waktu, yang dipisahkan oleh titik desimal. Thuse jika peristiwa terjadi dalam proses 1 dan 2, baik dengan waktu 40, mantan menjadi 40,1 dan yang terakhir datang 40,2.

Dengan menggunakan metode ini, kita sekarang memiliki cara untuk menetapkan waktu untuk semua kejadian dalam subjek sistem terdistribusi dengan kondisi berikut:

1.    Jika terjadi sebelum b dalam proses yang sama. C(a)

2.    JIKA dan b represent pengiriman dan receiveing pesan, masing masing Untuk semua kejadian distintive a dan b

3.    Algoritma ini memberi kita cara untuk menyediakan permintaan total semua kejadian dalam sistem. Banyak algoritma didistribusikan lainnya perlu memesan untuk menghindari ambiguitas, sehingga algoritma banyak dikutip dalam literatur.

Contoh:Totally Memerintahkan Multicasting

Sebagai aplikasi dari Lamport cap, mempertimbangkan situasi di mana database telah direplikasi di beberapa situs. Misalnya, untuk meningkatkan kinerja query, bank dapat menempatkan kinerja salinan, bank dapat menempatkan salinan database rekening di dua kota yang berbeda, misalnya New York dan San Fransisco. Sebuah permintaan selalu diteruskan ke salinan terdekat. Harga untuk respon yang cepat terhadap permintaan adalah pihak yang dibayar biaya pembaruan yang lebih tinggi, karena setiap operasi update harus dilakukan masing-masing replika.

Bahkan, ada persyaratan lebih strigent sehubungan dengan memperbarui. Asumsikan seorang pelanggan di San Francisco ingin menambahkan $ 100 sampai account-nya, yang curently mengandung 1,000 $. Pada saat yang sama, seorang karyawan bank di New York inisiat pembaruan dengan mana account pelanggan adalah untuk ditingkatkan dengan 1 persen bunga. Kedua update harus dilakukan keluar di kedua coppies dari database. Namun, disebabkan oleh keterlambatan komunikasi dalam jaringan yang mendasari, para update mungkin tiba dalam urutan seperti yang ditunjukkan pada Gbr.5-8.

Operasi update pelanggan dilakukan di San Francisco sebelum update bunga. Sebaliknya, salinan rekening di new york replika baru untuk pertama diperbarui dengan persen bunga saya, dan setelah itu dengan deposit $ 100. Akibatnya, san Database fransiscco akan mencatat jumlah total $1111, sedangkan database newyork catatan $1110.

Masalah yang kita hadapi adalah bahwa operasi dua pembaruan seharusnya dilakukan dalam urutan yang sama pada setiap copy. Meskipun itu membuat perbedaan apakah deposite diproses sebelum update bunga atau sebaliknya, yang order diikuti tidak penting dari sudut pandang konsistensi. Masalah penting adalah bahwa kedua salinan harus persis sama. Secara umum, situasi seperti ini memerlukan multicast benar-memerintahkan dalam mode sepenuhnya didistribusikan.

Pertimbangkan sekelompok proses multicasting pesan satu sama lain. Setiap pesan selalu timestamped dengan arus (logis) waktu pengirimnya. Ketika sebuah pesan multicast, maka secara konseptual juga dikirim ke pengirim. Selain itu, kami mengasumsikan bahwa pesan dari pengirim yang sama diterima dalam urutan mereka dikirim, dan bahwa tidak ada pesan yang hilang.

Ketika sebuah proses menerima pesan, itu dimasukkan ke dalam antrian lokal, memerintahkan menurut timestap nya. Penerima multicast suatu mengakui ke proses lainnya. Perhatikan bahwa jika kita mengikuti algoritma Lamport untuk menyesuaikan jam lokal, timestamp dari pesan yang diterima lebih rendah dari timestamp dari mengakui.

Aspek yang menarik dari pendekatan ini, adalah bahwa semua proses pada akhirnya akan memiliki salinan yang sama dari antrian lokal. Setiap pesan multicast untuk semua proses, termasuk pengakuan, dan diasumsikan akan diterima oleh semua proses. Ingat juga bahwa kita menganggap bahwa pesan yang disampaikan dalam urutan bahwa mereka akan dikirim. Setiap proses menempatkan pesan yang diterima dalam antrian lokal sesuai dengan timestamp dalam pesan itu. Jam Lamport ini memastikan bahwa tidak ada dua pesan memiliki timestamp yang sama, tetapi juga bahwa timestamp mencerminkan pemesanan global yang aconsistent peristiwa. Sebuah proses dapat menyampaikan pesan antri untuk aplikasi itu berjalan hanya bila pesan yang ada di kepala antrian dan telah diakui oleh setiap proses lain. Pada saat itu, pesan akan dihapus dari antrian dan diserahkan kepada aplikasi, ackwoledge terkait hanya dapat dihapus. Karena setiap proses memiliki salinan yang sama antrian, semua pesan yang disampaikan dalam everyehere urutan yang sama. Dengan kata lain, kami telah menetapkan benar - multicasting memerintahkan.

5.2.2 Cap vektor

Lamport timnestamp menyebabkan situasi semua kejadian dalam sistem terdistribusi secara total dipesan dengan properti yang jika peristiwa peristiwa yang terjadi sebelum acara b, maka juga akan diposisikan dalam memesan sebelum b, yaitu C (a) < C (b). Namun dengan Lamport cap, tidak ada yang dapat dikatakan tentang hubungan antara dua kejadian a dan b hanya dengan membandingkan waktu mereka nilai C (a) dan C (b), masing-masing. Dengan kata lain, jika C (a) <C (b), maka hal ini tidak selalu berarti bahwa memang terjadi sebelumnya b sesuatu yang lebih diperlukan untuk itu.

Untuk memahami apa yang sedang terjadi, mempertimbangkan sistem pesan di mana proses posting artikel dan bereaksi terhadap diposting articals. salah satu contoh yang paling populer seperti sistem pesan elektronik adalah layanan papan buletin internet itu, jaringan berita. Pengguna dan karenanya proses, bergabung dengan kelompok diskusi tertentu. Postingan dalam kelompok tersebut. posting kami dapat memutuskan untuk menggunakan skema multicasting benar-benar memerintahkan seperti penjelasan diatas.

Masalahnya adalah bahwa Lamport cap tidak menangkap causality.in contoh kita, penerimaan dari articale selalu kausal mendahului posting reaksi. akibatnya jika hubungan kausal yang dipertahankan kelompok withina proses, maka penerimaan reaksi terhadap artcale harus selalu mengikuti penerimaan dari artikel itu. Tidak lebih, tidak kurang. Jika dua artikel atau reaksi yang independen, pesanan mereka pengiriman seharusnya tidak masalah sama sekali.

Kausalitas dapat ditangkap dengan cara cap waktu vektor. Sebuah vektor timestamp VT (a) ditugaskan untuk sebuah acara memiliki properti bahwa jika VT (a) <VT (b) untuk beberapa acara b, maka acara yang diketahui kausal prcede acara b. waktu perangko vektor dibangun dengan membiarkan setiap proses pi mempertahankan vektor vi dengan dua sifat berikut:

1.    Vi[i] adalah jumlah peristiwa yang telah terjadi sejauh ini di pi.

2.    Jika Vi[j] = k maka pik nowns bahwa k peristiwa telah terjadi di pj.

Properti pertama dikelola oleh incrementing Vi [i] pada terjadinya setiap peristiwa baru yang happenes pada proses Pi properti kedua dipertahankan dengan membonceng vektor bersama dengan pesan yang dikirim. Secara khusus, ketika Pi mengirim pesan m, ia akan mengirimkan sepanjang arus vektor sebagai vt timestamp.

Dalam sebuah penerima informasi tentang jumlah kejadian yang telah terjadi di Pi. Lebih penting, namun adalah bahwa penerima diberitahu berapa banyak Avants pada proses lainnya telah terjadi sebelum Pi mengirim pesan m. dengan kata lain, cap vt m memberitahu penerima berapa banyak peristiwa di prosesses lain telah mendahului m, dan di mana m dapat kausal tergantung. Ketika proses pi menerima m, yang menyesuaikan vektor sendiri dengan menetapkan setiap entri Vj [k], untuk max {Vj [k], vt [k]}. Vektor sekarang mencerminkan jumlah pesan yang Pj harus menerima untuk memiliki setidaknya terlihat menjadi pesan yang sama yang mendahului pengiriman m. Hereaafter, entri Vj [t] bertambah dengan 1 mewakili hal menerima pesan berikutnya.

Dengan sedikit penyesuaian, cap vektor dapat digunakan untuk menjamin pesan causual delivery.Assume bahwa Vi [i] bertambah hanya ketika proses Pi mengirimkan pesan. Pertimbangkan lagi contoh sebuah papan buletin elektronik. Ketika posting Pi proses sebuah artikel, multicast artikel itu sebagai pesan dengan timestamp vt (a) ditetapkan sama dengan Vi.

Sekarang anggaplah posting Pi reaksi terhadap artikel. Hal ini dilakukan dengan multicasting r pesan dengan timestamp vt (r) ditetapkan sama dengan Vj. Perhatikan bahwa vt (r) [j] > vt(a)[j]. Dengan asumsi komunikasi yang handal, baik pesan tersebut berisi artikel, dan r pesan yang berisi reaksi akhirnya akan tiba di proses Pk lain. Seperti yang telah kita membuat tidak ada asumsi mengenai Urutan pesan, pesan r mungkin tiba di Pk sebelum pesan. Ketika menerima r, Pk menginspeksi timestamp vt (r) dan akan memutuskan untuk menunda pengiriman sampai semua pesan yang kausal mendahului r telah diterima juga. Secara khusus, pesan r disampaikan hanya jika kondisi berikut ini mte:

1.    Vt (r) [j] = Vk [j] +1

2.    Vt (r) [i] ≤ Vk [i] untuk semua i ≠ j

Kondisi pertama menyatakan bahwa r adalah pesan berikutnya yang Pk mengharapkan dari proses Pj. Yang kedua menyatakan bahwa kondisi Pk belum melihat adanya pesan yang tidak terlihat oleh Pj ketika ia mengirimkan pesan r. Secara khusus, ini berarti bahwa Pk telah melihat pesan.

Catatan tentang Memerintahkan Pengiriman Pesan

Beberapa sistem middleware, terutama ISIS dan Horus penggantinya (Birma dan van Renesse, 1994), memberikan dukungan untuk benar-benar-memerintahkan dan kausal-memerintahkan (terpercaya) multicasting. Ada beberapa kontroversi apakah dukungan tersebut harus disediakan sebagai bagian dari lapisan pesan-komunikasi, atau apakah aplikasi harus menangani pemesanan (Lihat, misalnya, Cheriton dan skeen, 1993, dan Birman, 1994).

Ada dua masalah utama dengan membiarkan komunikasi lapisan berurusan dengan pesan pemesanan. Pertama, karena menjadi lapisan komunikasi tidak bisa mengatakan apa pesan e sebenarnya mengandung, hanya potensial kausalitas ditangkap. Sebagai contoh, dua pesan dari pengirim yang sama yang benar-benar independen akan selalu ditandai sebagai kausal berkaitan dengan lapisan komunikasi. Pendekatan ini terlalu ketat dan dapat menyebabkan masalah efisiensi.

Masalah kedua adalah bahwa tidak semua kausalitas dapat ditangkap. Pertimbangkan lagi sistem berita. Misalkan Alice posting sebuah artikel. Jika dia kemudian telepon Bob bercerita tentang apa yang baru saja menulis, Bob dapat memposting artikel lain sebagai reaksi tanpa pernah melihat Alice posting di berita. Dengan kata lain, ada kausalitas antara Bob posting dan bahwa alice karena komunikasi eksternal. Kausalitas ini tidak ditangkap oleh sistem jaringan berita.

Pada intinya, memesan isu, seperti banyak masalah komunikasi aplikasi-spesifik lainnya, dapat secara memadai diselesaikan dengan melihat aplikasi mana komunikasi berlangsung dapat, ini juga dikenal sebagai argumen end-to-end dalam sistem desain (Saltzer dkk ., 1984). Sebuah kelemahan hanya memiliki solusi tingkat aplikasi, adalah bahwa pengembang dipaksa untuk berkonsentrasi pada masalah yang tidak segera berhubungan dengan fungsi inti dari aplikasi. Misalnya, pemesanan mungkin tidak menjadi masalah yang paling penting ketika mengembangkan sistem pesan seperti berita jaringan. Dalam hal ini, memiliki komunikasi yang mendasari lapisan menangani pemesanan dapat berubah menjadi nyaman. Kami akan datang di end-to-end argumen beberapa kali, terutama ketika berhadapan dengan keamanan pada sistem terdistribusi.

5.3 Global State

Ketika jumlah node dalam sebuah sistem terdistribusi tumbuh, menjadi semakin sulit bagi setiap node untuk melacak orang lain. Pengetahuan tersebut dapat penting untuk melaksanakan algoritma terdistribusi seperti routing, multicasting, data penempatan, mencari, dan sebagainya. Kita telah melihat contoh-contoh yang berbeda dalam yang koleksi besar node diatur dalam topologi tertentu yang memfasilitasi pelaksanaan efisien algoritma tersebut. Pada bagian ini, kita melihat pada organisasi lain yang berhubungan dengan masalah waktu.

Dalam jaringan overlay geometrik setiap node diberi posisi di 111  dimensi geometris ruang, sehingga jarak antara dua node dalam ruang mencerminkan kinerja dunia nyata metrik. Yang paling sederhana, dan paling diterapkan Sebagai contoh, adalah di mana jarak sesuai dengan internode latency. Dengan kata lain. diberikan dua node P dan Q, maka jarak d (P, Q) mencerminkan berapa lama itu akan mengambil untuk pesan ke perjalanan dari P ke Q dan sebaliknya.

Ada banyak aplikasi jaringan overlay geometris. Pertimbangkan situasi di mana sebuah situs web di server 0 telah direplikasi ke beberapa server S} "". Sk di Internet. Ketika sebuah klien meminta halaman C dari 0, yang kedua mungkin memutuskan untuk mengarahkan permintaan itu ke server terdekat dengan C, yaitu, salah satu yang akan memberikan waktu respon yang terbaik. Jika lokasi geometrik C dikenal, serta orang-orang dari setiap server replika, 0 kemudian dapat hanya memilih server S, yang d (C, SJ adalah minimal. Perhatikan bahwa seperti pilihan hanya membutuhkan pemrosesan lokal di O. Dengan kata lain, ada, misalnya, tidak perlu sampel semua latency antara C dan masing-masing server replika.

Contoh lain, yang kita akan bekerja secara rinci dalam bab berikutnya, adalah optimal replika penempatan. Pertimbangkan lagi situs Web yang telah mengumpulkan posisi kliennya. Jika situs itu untuk meniru isinya ke server K, dapat menghitung K terbaik posisi di mana untuk menempatkan replika sehingga rata-rata klien-toreplica waktu respon minimal. Melakukan perhitungan tersebut hampir sepele layak jika klien dan server memiliki posisi geometris yang mencerminkan latency ruas.

Sebagai contoh terakhir, mempertimbangkan posisi berbasis routing (Araujo dan Rodrigues, 2005, dan Stojmenovic, 2002). Dalam skema tersebut, pesan diteruskan ke nya tujuan menggunakan informasi posisi saja. Sebagai contoh, sebuah algoritma routing yang naif untuk membiarkan setiap node meneruskan pesan ke tetangga yang paling dekat dengan tujuan. Meskipun dapat dengan mudah menunjukkan bahwa algoritma tertentu tidak perlu bertemu,menggambarkan bahwa informasi lokal hanya digunakan untuk mengambil keputusan. Ada tidak perlu untuk menyebarkan informasi tersebut kepada link atau semua node dalam jaringan, seperti kasus dengan algoritma routing konvensional.

Secara teoritis, posisi node di ruang m-dimensi geometris membutuhkan
m tindakan jarak +1 ke node dengan posisi yang dikenal. Hal ini dapat dengan mudah dilihat dengan mempertimbangkan kasus m = 2, seperti ditunjukkan pada Gambar. 6-18. Dengan asumsi bahwa P simpul ingin menghitung posisinya sendiri, kontak tiga node lain dengan posisi yang dikenal dan mengukur jarak ke masing-masing.

P memberitahu tentang lingkaran itu terletak di; menghubungi hanya dua node akan menceritakannya tentang posisi persimpangan dua lingkaran (yang umumnya terdiri dari dua poin), sebuah simpul ketiga selanjutnya akan memungkinkan P untuk menghitung adalah lokasi sebenarnya.

Seperti dikatakan, d, umumnya sesuai dengan mengukur latency antara P dan simpul di (Xj, YJ. latency ini dapat diperkirakan sebagai setengah penundaan round-trip, tetapi harus jelas bahwa nilainya akan berbeda dari waktu ke waktu. Efeknya adalah berbeda posisi kapanpun P ingin recompute posisinya. Apalagi, jika node lain akan menggunakan posisi P untuk menghitung koordinat mereka sendiri, kemudian itu harus jelas bahwa kesalahan dalam posisi P akan mempengaruhi keakuratan posisi node lain.

5.4 PEMILIHAN ALGORITMA

Algoritma didistribusikan Banyak memerlukan satu proses untuk bertindak sebagai koordinator, inisiator, atau melakukan beberapa peran khusus. Secara umum, tidak peduli yang Proses ini mengambil tanggung jawab khusus, tapi salah satu dari mereka harus melakukannya. dalam hal ini bagian ini kita akan melihat algoritma untuk memilih seorang koordinator (menggunakan ini sebagai generik nama untuk proses khusus).

Jika semua proses yang persis sama, tanpa membedakan karakteristik,
tidak ada cara untuk memilih salah satu dari mereka untuk menjadi istimewa. Akibatnya, kita akan mengasumsikan bahwa setiap proses memiliki nomor yang unik, misalnya, alamat jaringan nya (untuk kesederhanaan, kita akan mengasumsikan satu proses per mesin). Secara umum algoritma pemilu, berusaha untuk menemukan proses dengan nomor proses tertinggi dan menetapkannya sebagai koordinator. Algoritma berbeda dalam cara mereka lakukan lokasi.

Selain itu, kami juga menganggap bahwa setiap proses mengetahui jumlah proses setiap proses lainnya. Apa proses tidak tahu adalah mana yang. sekarang
yang naik dan yang turun saat ini. Tujuan dari algoritma pemilu adalah untuk memastikan bahwa ketika pemilihan dimulai, diakhiri dengan semua proses setuju pada siapa koordinator baru adalah menjadi. Ada banyak algoritma dan variasi, yang yang penting yang dibahas dalam buku-buku teks dengan Lynch (l996) dan Tel (2000), masing-masing.

5.4.1 The Bully Algorithm

            Sebagai contoh pertama, mempertimbangkan algoritma pengganggu yang dibuat oleh Garcia-Molina (1982). Bila sebuah proses mendapatkan coordinator tidak lagi menanggapi request yang dikirim, maka proses pemilihan akan diinisiasi. Proses P mengadakan pemilihan sebagai berikut:

1.    P mengirim pesan ELECTION ke semua proses dengan nomor proses yang lebih besar.

2.    Bila tidak ada tanggapan, proses P memenangkan pemilihan dan menjadi koordinator.

3.    Namun bila salah satu proses dengan nomor yang lebih tinggi menjawab, proses tesebutlah yang akan mengambil alih proses pemilihan. Pekerjaan prosess P sendiri selesai disini.

Setiap saat, proses bisa mendapatkan pesan PEMILIHAN dari salah satu nya rendah-nomor rekan. Bila pesan seperti itu tiba, penerima mengirimkan Pesan kembali ke pengirim OK untuk menunjukkan bahwa ia masih hidup dan akan mengambil alih. Itu penerima kemudian memegang pemilu, kecuali sudah memegang satu. Akhirnya, semua proses menyerah tapi satu, dan yang satu adalah koordinator baru. Ini mengumumkan nya Kemenangan dengan mengirimkan semua proses pesan mengatakan kepada mereka bahwa mulai segera itu adalah koordinator baru.

Jika proses yang sebelumnya turun datang kembali, memegang pemilu. Jika akan terjadi pada proses tertinggi bernomor sedang berjalan, maka akan memenangkan pemilu dan mengambil alih pekerjaan koordinator. Dengan demikian orang terbesar di kota selalu menang, maka nama "algoritma pengganggu."

Dalam Gambar. 6-20 kita melihat contoh bagaimana algoritma bully bekerja. Kelompok terdiri dari delapan proses, nomor dari 0 sampai 7. Sebelumnya proses 7 adalah koordinator, tetapi baru saja jatuh. Proses 4 adalah yang pertama untuk melihat ini, sehingga mengirimkan pesan PEMILU bagi semua proses yang lebih tinggi dari itu, yaitu 5, 6, dan 7. seperti yang ditunjukkan pada Gambar. 6-20 (a). Proses 5 dan 6 keduanya merespon dengan OK, seperti yang ditunjukkan pada Gambar. 6-20 (b). Setelah mendapatkan pertama dari tanggapan, 4 tahu bahwa tugasnya adalah atas. Ia tahu bahwa salah satu petinggi akan mengambil alih dan menjadi koordinator. Itu hanya duduk kembali dan menunggu untuk melihat siapa pemenangnya akan (meskipun pada titik ini dapat membuat perkiraan yang cukup baik).

Sebuah Algoritma Cincin

            Lain algoritma pemilihan didasarkan pada penggunaan cincin. Tidak seperti beberapa algoritma cincin, satu ini tidak menggunakan token. Kami berasumsi bahwa proses secara fisik atau logis memerintahkan, sehingga setiap proses tahu siapa penggantinya adalah. Ketika setiap proses pemberitahuan bahwa koordinator tidak berfungsi, itu membangun suatu PEMILU pesan yang berisi nomor proses sendiri dan mengirimkan pesan ke 'nya penggantinya. Jika penggantinya sedang down, pengirim melompat lebih penerus dan pergi ke anggota berikutnya di sepanjang cincin. atau satu setelah itu, sampai proses yang berjalan adalah terletak. Pada setiap langkah di sepanjang jalan, pengirim menambahkan nomor proses sendiri untuk daftar di pesan secara efektif membuat dirinya calon yang akan terpilih sebagai koordinator.

            Akhirnya, pesan akan kembali ke proses yang memulai semuanya. proses
mengakui acara ini ketika menerima pesan masuk yang berisi nya
sendiri proses nomor. Pada saat itu, jenis pesan diubah menjadi KOORDINATOR
dan beredar sekali lagi, kali ini untuk menginformasikan orang lain yang koordinator adalah (anggota daftar dengan jumlah tertinggi) dan siapa para anggota cincin baru. Ketika pesan ini sudah beredar sekali, itu akan dihapus dan semua orang kembali bekerja