TIME AND GLOBAL STATES

DISTRIBUTED SYSTEMS Concept and Design – Fifth Edition
George Coulouris
Cambridge University
Jean Dollimore
formerly of Queen Mary, University of London
Tim Kindberg
matter 2 media
Gordon Blair
Lancaster University

Dalam bab ini, kami memperkenalkan beberapa topik yang terkait dengan masalah waktu di terdistribusi sistem. Waktu adalah masalah praktis yang penting. Sebagai contoh, kita memerlukan komputer di seluruh dunia untuk timestamp transaksi perdagangan elektronik secara konsisten. Waktu juga merupakan konstruk teoritis penting dalam memahami bagaimana eksekusi didistribusikan terungkap. Tapi Waktu yang bermasalah dalam sistem terdistribusi. Setiap komputer mungkin memiliki fisik sendiri Jam, tapi jam biasanya menyimpang, dan kita tidak dapat melakukan sinkronisasi dengan sempurna.
Kami memeriksa algoritma untuk sinkronisasi jam fisik sekitar dan kemudian pergi ke menjelaskan jam logis, termasuk jam vektor, yang merupakan alat untuk memesan acara tanpa mengetahui tepatnya ketika mereka terjadi. Tidak adanya waktu fisik global yang membuat sulit untuk mengetahui keadaan kami

didistribusikan program karena mereka mengeksekusi. Kita sering perlu tahu apa negara proses A di ketika proses B dalam keadaan tertentu, tetapi kita tidak bisa mengandalkan jam fisik untuk mengetahui apa benar pada waktu yang sama. Bagian kedua dari bab ini membahas algoritma untuk menentukan negara global perhitungan didistribusikan meskipun kurangnya waktu global.



Introduction
Memperkenalkan konsep dasar dan algoritma terkait dengan pemantauan sistem terdistribusi sebagai eksekusi mereka terungkap, dan untuk waktu peristiwa yang terjadi di mereka eksekusi. Waktu adalah masalah penting dan menarik di sistem terdistribusi, untuk beberapa alasan. Pertama, waktu adalah kuantitas kita sering ingin mengukur secara akurat. Untuk mengetahui apa waktu hari peristiwa tertentu terjadi pada komputer tertentu perlu menyinkronkan jam dengan berwibawa, sumber eksternal waktu. Sebagai contoh, sebuah transaksi eCommerce melibatkan peristiwa di komputer pedagang dan pada bank komputer. Hal ini penting, untuk tujuan audit, yang peristiwa-peristiwa yang waktu dicap akurat.Kedua, algoritma yang bergantung pada sinkronisasi jam telah dikembangkan untuk beberapa masalah dalam distribusi [Liskov 1993].

Ini termasuk menjaga konsistensi data terdistribusi (penggunaan cap waktu untuk cerita transaksi adalah dibahas dalam Bagian 16,6), memeriksa keaslian permintaan dikirim ke server (aversi Kerberos protokol otentikasi, dibahas dalam Bab 11, tergantung pada longgar disinkronkan jam) dan menghilangkan pengolahan duplikat update (lihat,misalnya, Ladin et al. [1992]). Mengukur waktu dapat menjadi masalah karena adanya beberapa frame dari referensi. Einstein menunjukkan, dalam Teori Relativitas Khusus, yang menarik konsekuensi yang mengikuti dari pengamatan bahwa kecepatan cahaya adalah konstan untuk semua pengamat, terlepas dari kecepatan relatif mereka. Ia membuktikan dari asumsi ini, antara hal-hal lain, bahwa dua peristiwa yang dinilai tidak simultan dalam satu kerangka acuan belum tentu simultan menurut pengamat dalam bingkai acuan lain yang bergerak relatif terhadap itu. Sebagai contoh, seorang pengamat di Bumi dan pengamat bepergian jauh dari Bumi dalam pesawat ruang angkasa akan tidak setuju pada interval waktu antaraperistiwa, lebih-lebih sebagai kecepatan relatif mereka meningkat.

Urutan relatif dua peristiwa bahkan dapat dihilangkan untuk dua pengamat yang berbeda.Tapi ini tidak bisa terjadi jika salah satu acara menyebabkan yang lain terjadi. Dalam hal ini, fisik Efek mengikuti penyebab fisik untuk semua pengamat, meskipun waktu berlalu antara sebab dan akibat dapat bervariasi. Waktu kejadian fisik demikian terbukti relative ke pengamat, dan gagasan Newton tentang waktu fisik mutlak terbukti tanpa dasar.  Tidak ada jam fisik khusus di alam semesta yang kita dapat naik banding ketika kita ingin mengukur interval waktu Gagasan waktu fisik juga bermasalah dalam sistem terdistribusi. Ini bukan karena efek dari relativitas khusus, yang diabaikan atau tidak ada untuk normal komputer (kecuali satu jumlah komputer bepergian di ruang angkasa!). Sebaliknya, masalah didasarkan pada batasan yang sama dalam kemampuan kita untuk timestamp acara di node yang berbeda cukup akurat untuk mengetahui urutan di mana setiap pasangan peristiwa terjadi, atau apakah mereka terjadi secara bersamaan. Tidak ada yang mutlak, waktu global yang kita dapat mengajukan banding. Namun kadang-kadang kita perlu mengamati sistem terdistribusi dan membangun apakah negara-negara tertentu urusan terjadi pada waktu yang sama. Misalnya, di objectoriented sistem kita harus mampu untuk menentukan apakah referensi ke objek tertentu tidak ada lagi - apakah objek telah menjadi sampah (dalam hal ini kita dapat membebaskan ingatan). Membentuk ini membutuhkan pengamatan dari negara bagian proses (untuk mengetahui apakah mereka mengandung referensi) dan saluran komunikasi antara proses (Dalam pesan kasus yang berisi referensi dalam transit). Pada paruh pertama bab ini, kita akan mengkaji metode dimana jam komputer bisa akan sekitar disinkronkan, menggunakan pesan lewat. Kami pergi untuk memperkenalkan logis jam, termasuk jam vektor, yang digunakan untuk menentukan urutan peristiwa tanpa mengukur waktu fisik di mana mereka terjadi. Di babak kedua, kami menjelaskan algoritma yang tujuannya adalah untuk menangkap dunia negara sistem terdistribusi karena mereka mengeksekusi



Clocks, events and process states
Disajikan model pengantar dari interaksi antara proses dalam sistem terdistribusi. Di sini kita memperbaiki model yang untuk membantu kita untuk memahami bagaimana ciri evolusi sistem sebagai dijalankan, dan bagaimana timestamp peristiwa dalam eksekusi sistem yang pengguna bunga. Kita mulai dengan mempertimbangkan cara memesan dan timestamp peristiwa yang terjadi pada proses tunggal. Kami mengambil sistem terdistribusi terdiri dari koleksi ?? proses Npi? i = Setiap proses e 1 2? ? } N. mengeksekusi pada prosesor tunggal, dan prosesor melakukantidak berbagi memori (Bab 6 sempat mempertimbangkan kasus proses yang berbagiingatan). Setiap pi proses ?? memiliki si negara itu, secara umum, itu mengubah karenamengeksekusi. Proses ini negara termasuk nilai-nilai semua variabel di dalamnya. Negaranya juga dapat mencakup nilai-nilai dari setiap benda di lingkungan sistem operasi lokal yang itu mempengaruhi, seperti file. Kami berasumsi bahwa proses tidak dapat berkomunikasi dengan satu sama lain dengan cara apapun kecuali dengan mengirimkan pesan melalui jaringan. Jadi, misalnya, jika proses mengoperasikan lengan robot terhubung ke node masing-masing dalam sistem, maka mereka tidak diizinkan untuk berkomunikasi dengan menggoyangkan satu tangan robot sama lain! Seperti setiap proses pi mengeksekusi dibutuhkan serangkaian tindakan, yang masing-masing baik pesan mengirim atau menerima operasi, atau operasi yang mengubah negara pi 's – yang perubahan satu atau lebih dari nilai-nilai di si. Dalam prakteknya, kita dapat memilih untuk menggunakan tingkat tinggi deskripsi tindakan, sesuai dengan aplikasi. Misalnya, jika proses di ?? terlibat dalam sebuah aplikasi eCommerce, maka tindakan mungkin yang seperti 'Client mengirimkan perintah pesan' atau 'server pedagang mencatat transaksi login'. Kita mendefinisikan sebuah acara untuk menjadi terjadinya tindakan tunggal yang proses membawa sebagai dijalankan - tindakan komunikasi atau tindakan negara-mentransformasikannya. Urutan peristiwa dalam proses pi tunggal dapat ditempatkan dalam satu, jumlah pemesanan, yang kami dilambangkan dengan hubungan oi antara peristiwa. Artinya, e oi e 'jika dan hanya jika acara e terjadi sebelum ec di pi . pemesanan ini didefinisikan dengan baik, apakah proses multithreaded, karena kita telah mengasumsikan bahwa proses mengeksekusi pada prosesor tunggal.Sekarang kita dapat mendefinisikan sejarah proses pi menjadi rangkaian acara yang mengambil tempatkan di dalamnya, memerintahkan seperti yang kita telah dijelaskan oleh hubungan oi: sejarah (pi hi <ei0 ei1 ei2 = = ??? }>Jam • Kita telah melihat bagaimana untuk memesan acara di proses, tapi tidak bagaimana timestamp mereka - yaitu, untuk menetapkan mereka tanggal dan waktu hari. Komputer masing-masing berisi sendiri jam fisik. jam ini adalah perangkat elektronik yang menghitung osilasi yang terjadi

        kristal pada frekuensi tertentu, dan biasanya membagi hitungan ini dan menyimpan hasilnya dalam sebuah kontra mendaftar. perangkat jam dapat diprogram untuk menghasilkan interupsi di regular interval agar, misalnya, waktu mengiris dapat diimplementasikan; Namun, kami akan tidak menyibukkan diri dengan aspek operasi jam. Sistem operasi membaca nilai jam hardware node, Hi ? t, skala dan menambahkan offset sehingga menghasilkan jam software Ci ? D t Hi = itu appro? E t + ximately mengukur nyata, fisik waktu t untuk proses pi. Dengan kata lain, ketika real time dalam bingkai mutlak acuan adalah t, Ci ? t adalah membaca pada jam software. Sebagai contoh, ci ? t bisa menjadi nilai 64-bit dari jumlah nanodetik yang telah berlalu pada waktu t karena waktu referensi nyaman. Secara umum, jam tidak sepenuhnya akurat, sehingga ci ? t akan berbeda dari t. Meskipun demikian, jika Ci berperilaku cukup baik (kita akan memeriksa gagasan jam kebenaran lama), kita dapat menggunakan nilai untuk timestamp acara samapi. Perhatikan bahwa kejadian yang beruntun akan sesuai dengan cap waktu yang berbeda hanya jika jam. Resolusi - periode antara update dari nilai jam - lebih kecil dari waktu interval antara kejadian yang beruntun. Tingkat di mana peristiwa terjadi tergantung pada seperti faktor sebagai panjang dari siklus instruksi prosesor. Jam condong dan pergeseran jam • jam komputer, seperti orang lain, cenderung tidak berada di sempurna perjanjian.

Skew antara jam komputer dalam sistem terdistribusi Jaringan ). Sesaat perbedaan antara pembacaan dua jam disebut condong mereka. Juga, jam berbasis kristal yang digunakan dalam komputer, seperti jam lainnya, tunduk pada jam drift, yang berarti bahwa mereka menghitung waktu pada tingkat yang berbeda, dan menyimpang.

Osilator mendasari dikenakan variasi fisik, dengan konsekuensi bahwa frekuensi mereka osilasi berbeda. Selain itu, bahkan sama frekuensi clock bervariasi dengan suhu. Desain ada yang mencoba untuk mengkompensasi variasi ini, tetapi mereka tidak bisa menghilangkannya. Perbedaan pada periode osilasi antara dua jam mungkin sangat kecil, tetapi perbedaan akumulasi lebih dari banyak osilasi menyebabkan perbedaan diamati di counter terdaftar oleh dua jam, tidak peduli seberapa akurat mereka diinisialisasi dengan nilai yang sama. hanyut Jam ini Tingkat adalah perubahan offset (perbedaan dalam membaca) antara jam dan nominal referensi jam sempurna per unit waktu diukur dengan jam referensi. untuk biasa jam berdasarkan kristal kuarsa ini adalah tentang 10-6 detik / detik, memberikan perbedaan 1 detik setiap 1.000.000 detik, atau 11,6 hari. Tingkat drift 'presisi tinggi' jam kuarsa adalah sekitar 10-7 atau 10-8.

Coordinated Universal Time • jam komputer dapat disinkronkan dengan sumber eksternal waktu yang sangat akurat. Jam fisik yang paling akurat menggunakan osilator atom, yang Tingkat drift sekitar satu bagian dalam 1013. Output ini jam atom digunakan sebagai BAGIAN 14.3 Sinkronisasi FISIK JAM 599 standar untuk berlalu real time, yang dikenal sebagai Waktu Atom Internasional. Sejak tahun 1967, standar kedua telah didefinisikan sebagai 9192631770 periode transisi antara dua tingkat hyperfine dari keadaan dasar dari Cesium-133 (Cs133). Detik dan tahun dan unit waktu lain yang kami gunakan berakar pada astronomi waktu. Mereka awalnya didefinisikan dalam hal rotasi bumi pada porosnya dan rotasi tentang Sun. Namun, periode rotasi bumi pada porosnya adalahsecara bertahap semakin panjang, terutama karena gesekan pasang surut; efek atmosfer dan arus konveksi dalam inti Bumi juga menyebabkan kenaikan jangka pendek dan menurun pada periode. Jadi waktu astronomi dan waktu atom memiliki kecenderungan untuk keluar langkah.

Coordinated Universal Time - disingkat UTC (dari Perancis setara) Merupakan standar internasional untuk ketepatan waktu. Hal ini didasarkan pada waktu atomik, tapi yang disebut 'Lompatan kedua' disisipkan - atau, lebih jarang, dihapus - kadang-kadang untuk tetap pada langkah dengan waktu astronomi. sinyal UTC disinkronisasi dan disiarkan secara teratur dari landbased Stasiun radio dan satelit yang mencakup banyak bagian dunia. Misalnya, dalam USA, stasiun radio WWV waktu siaran sinyal pada beberapa frekuensi gelombang pendek. Sumber

Satelit termasuk Global Positioning System (GPS).

Penerima tersedia secara komersial. Dibandingkan dengan 'sempurna' UTC, sinyal yang diterima dari stasiun darat memiliki akurasi atas perintah 0,1-10 milidetik, tergantung pada stasiun yang digunakan. Sinyal yang diterima dari satelit GPS yang akurat untuk sekitar 1 mikrodetik. Komputer dengan receiver terpasang dapat menyinkronkan jam mereka dengan sinyal-sinyal waktu.

Synchronizing physical clocks
Untuk mengetahui apa saat kejadian hari terjadi pada proses di kami didistribusikan sistem ?? - Misalnya, untuk tujuan akuntansi - perlu untuk menyinkronkan jam proses ', Ci, dengan berwibawa, sumber eksternal waktu. Ini adalah eksternal sinkronisasi. Dan jika jam Ci disinkronkan dengan satu sama lain untuk diketahui tingkat akurasi, maka kita dapat mengukur interval antara dua peristiwa yang terjadi di komputer yang berbeda dengan menarik jam lokal mereka, meskipun mereka tidak tentu disinkronkan dengan sumber eksternal waktu. Ini adalah sinkronisasi internal. Kita mendefinisikan dua mode sinkronisasi lebih dekat sebagai berikut, pada interval dari real time I:

sinkronisasi eksternal: Untuk sinkronisasi terikat D! 0, dan untuk sumber S dari UTC waktu, S t? Ci -? t <D, untuk i = 1 2? ? } N dan untuk semua nyata kali t di I. lain cara untuk mengatakan ini adalah bahwa jam Ci akurat ke dalam D. terikat

sinkronisasi internal: Untuk sinkronisasi terikat D! 0, Ci ? t Cj -? t? D untuk i j? =, Dan untuk semua nyata ti 1 2? ? } N mes t di I. Cara lain untuk mengatakan ini adalah bahwa jam ci setuju dalam D.

terikat Jam yang disinkronkan internal tidak selalu eksternal disinkronkan, karena mereka dapat melayang kolektif dari sumber eksternal waktu meskipun mereka setuju satu sama lain. Namun, mengikuti dari definisi bahwa jika sistem ??

Eksternal disinkronkan dengan D terikat, maka sistem yang sama secara internal disinkronkan dengan terikat 2D. Berbagai pengertian tentang kebenaran untuk jam telah diusulkan. Hal ini umum untuk mendefinisikan hardware jam H menjadi benar jika tingkat penyimpangan yang jatuh dalam batas U dikenal !? (Nilai yang berasal dari satu dipasok oleh produsen, seperti 10-6 detik / detik). Ini berarti bahwa kesalahan dalam mengukur interval antara nyata kali t dan tc (tc! T) adalah dibatasi: ?

1 - U? tc - t d H t? c - H t? d? 1 + U? tc – t

Kondisi ini melarang melompat di nilai jam hardware (selama operasi normal). Kadang-kadang kita juga memerlukan jam perangkat lunak kami untuk mematuhi kondisi tapi lemah kondisi monotonicity mungkin cukup. Monotonicity adalah kondisi yang jam C hanya pernah kemajuan: tc! t ?? C t? c! C t?

Misalnya, fasilitas make UNIX adalah alat yang digunakan untuk mengkompilasi satunya sumber mereka file yang telah dimodifikasi sejak mereka terakhir dikompilasi. Tanggal modifikasi setiap pasangan yang sesuai dari sumber dan objek file dibandingkan untuk menentukan ini kondisi.

Jika komputer yang jam itu berjalan cepat mengatur jam-nya kembali setelah kompilasi file sumber tapi sebelum berkas berubah, file sumber mungkin tampaknya telah dimodifikasi sebelum kompilasi. Keliru, membuat tidak akan mengkompilasi ulang file sumber. Kita dapat mencapai monotonicity meskipun fakta bahwa jam ditemukan akan berjalan cepat. Kita hanya perlu mengubah tingkat di mana update dibuat untuk waktu yang diberikan kepada aplikasi. Hal ini dapat dicapai dalam perangkat lunak tanpa mengubah tingkat di mana mendasari jam hardware kutu - ingat bahwa Ci ? D t Hi =, di mana kita bebas untuk? E t + memilih nilai-nilai D dan E. Sebuah kondisi kebenaran hybrid yang kadang-kadang diterapkan adalah dengan mengharuskan jam mematuhi kondisi monotonicity, dan bahwa tingkat penyimpangan yang dibatasi antara poin sinkronisasi, tetapi untuk memungkinkan nilai jam untuk melompat ke depan pada sinkronisasi poin.

Sebuah jam yang tidak menjaga kondisi kebenaran apa pun berlaku didefinisika menjadi rusak. Kegagalan kecelakaan Jam ini dikatakan terjadi ketika jam berhenti berdetak sama sekali; kegagalan jam lainnya adalah kegagalan yang sewenang-wenang. Sebuah contoh sejarah dari kegagalan sewenang-wenang  adalah bahwa dari sebuah jam dengan 'bug Y2K', yang memecahkan kondisi monotonicity oleh mendaftar tanggal setelah tanggal 31 Desember 1999 sebagai 1 Januari 1900 bukan 2000; lain Contohnya adalah sebuah jam yang baterai sangat rendah dan tingkat hanyut yang tiba-tiba menjadi sangat besar. Perhatikan bahwa jam tidak harus akurat untuk menjadi benar, sesuai dengan definisi. Sejak tujuan mungkin internal daripada sinkronisasi eksternal, kriteria untuk kebenaran hanya berkaitan dengan berfungsinya jam itu 'Mekanisme', bukan pengaturan mutlak. Kami sekarang menggambarkan algoritma untuk sinkronisasi eksternal dan untuk intern sinkronisasi.

Sinkronisasi dalam sistem sinkron
Kita mulai dengan mempertimbangkan kasus yang paling sederhana mungkin: sinkronisasi internal antara dua proses dalam sistem terdistribusi sinkron. Dalam sistem sinkron, batas yang dikenal untuk tingkat drift jam, keterlambatan transmisi pesan maksimum, dan waktu yang dibutuhkan untuk melaksanakan setiap langkah dari proses (lihat Bagian 2.4.1). Salah satu proses mengirim waktu t pada jam lokal yang lain dalam pesan m. Di Prinsip, proses penerimaan bisa mengatur jam untuk waktu t Ttrans +, di mana Ttrans adalah waktu yang dibutuhkan untuk mengirimkan m di antara mereka. Dua jam kemudian setuju (sejak Tujuan adalah sinkronisasi internal tidak peduli apakah jam proses pengiriman ini akurat). Sayangnya, Ttrans tunduk pada variasi dan tidak diketahui. Secara umum, lainnya proses bersaing untuk sumber daya dengan proses yang akan disinkronisasi di mereka masing node, dan pesan lainnya bersaing dengan m untuk sumber daya jaringan.

Meskipun demikian, selalu ada waktu transmisi minimum, min, yang akan diperoleh jika tidak ada proses lain dijalankan dan tidak ada lalu lintas jaringan lainnya ada; min dapat diukura tau konservatif diperkirakan. Dalam sistem sinkron, menurut definisi, ada juga max batas atas waktu yang dibutuhkan untuk mengirimkan pesan apapun. Biarkan ketidakpastian dalam waktu transmisi pesan

u, sehingga u max min =. Jika penerima menetapkan cloc nya? - K menjadi t min +, maka

jam condong mungkin sebanyak u, karena pesan mungkin sebenarnya telah mengambil waktu max untuk tiba. Demikian pula, jika ia menetapkan jam untuk t max +, condong mungkin lagi sebagai besar sebagai u. Jika, Namun, ia menetapkan jam untuk titik tengah, t max min +? + E 2, maka condong berada pada paling u e 2. Secara umum, untuk sistem sinkron, optimal terikat yang dapat dicapai pada jam condong saat sinkronisasi jam N adalah u? 1 1 - e N [Lundelius dan Lynch 1984].

sistem yang paling didistribusikan ditemukan dalam praktek adalah asynchronous: faktor yang menyebabkan pesan penundaan tidak dibatasi dalam efeknya, dan tidak ada max batas atas penundaan transmisi pesan. Hal ini khususnya terjadi untuk Internet. Untuk sebuah sistem asynchronous, kita dapat mengatakan hanya itu Ttrans =, di mana min x + x ?? 0. Nilai x tidak diketahui dalam kasus tertentu, meskipun distribusi nilai mungkin terukur untuk instalasi tertentu.

3.2 Cristian [ 1989 ]







Cristian mengamati bahwa sementara tidak ada batas atas pada keterlambatan transmisi pesan di sistem asynchronous, kali pulang-pergi untuk pesan yang dipertukarkan antara pasangan proses sering cukup singkat - sebagian kecil dari kedua. Dia menjelaskan algoritma sebagai probabilistik: metode mencapai sinkronisasi hanya jika diamati kali pulang-pergi antara klien dan server yang cukup singkat dibandingkan dengan akurasi yang diperlukan.

Sebuah proses p meminta waktu dalam mr pesan, dan menerima nilai waktu t dalam mt pesan (t dimasukkan dalam mt pada kemungkinan titik terakhir sebelum transmisi dari S komputer). Proses p mencatat total waktu round-trip Tround diambil untuk mengirim permintaan mr dan menerima balasan mt. Hal ini dapat mengukur waktu ini dengan cukup akurat jika tingkat jam drift kecil. Misalnya, waktu pulang-pergi harus pada urutan 1-10 milidetik pada LAN, di mana waktu jam dengan tingkat drift 10-6 detik / detik bervariasi oleh paling 10-5 milidetik.

Perkiraan sederhana dari waktu yang p harus mengatur jam adalah t Tround +, e 2 yang mengasumsikan bahwa waktu berlalu dibagi sama sebelum dan sesudah S ditempatkan t di mt. Hal ini biasanya asumsi cukup akurat, kecuali dua pesan yang ditransmisikan melalui jaringan yang berbeda. Jika nilai transmisi minimum waktu min dikenal atau dapat konservatif diperkirakan, maka kita dapat menentukan akurasi ini hasil sebagai berikut.

Titik awal di mana S bisa ditempatkan waktu di mt adalah menit setelah p dikirim mr. Titik terbaru di mana ia bisa melakukan ini adalah menit sebelum mt tiba di p. Oleh karena itu waktu dengan jam S ketika pesan balasan tiba berada diKisaran t min + tT [,]. Lebar ini berlari + bulat - min ge adalah Tround -, sehingga 2 menit yang akurasi ± Tround? e 2 - min.

Variabilitas dapat ditangani dengan sampai batas tertentu dengan membuat beberapa permintaan untuk S (Spasi permintaan sehingga kemacetan sementara dapat menghapus) dan mengambil minimum. Nilai Tround untuk memberikan perkiraan yang paling akurat. Semakin besar akurasi yang diperlukan, semakin kecil kemungkinan untuk mencapai itu. Hal ini karena hasil yang paling akurat.  Mereka di mana kedua pesan yang dikirim dalam waktu dekat min - sebuah peristiwa tidak mungkin dalam jaringan yang sibuk.

Diskusi algoritma Cristian • Seperti dijelaskan, metode Cristian menderita Masalah yang terkait dengan semua layanan dilaksanakan oleh server tunggal: bahwa waktu tunggal Server mungkin gagal dan dengan demikian membuat sinkronisasi sementara mustahil. Cristian disarankan, untuk alasan ini, waktu yang harus disediakan oleh sekelompok waktu disinkronkan server, masing-masing dengan receiver untuk sinyal waktu UTC. Misalnya, klien bisa multicast Permintaannya untuk semua server dan menggunakan hanya yang pertama jawaban yang diperoleh.

Perhatikan bahwa server waktu rusak yang menjawab dengan nilai-nilai waktu palsu, atau penipu ulung waktu server yang menjawab dengan kali sengaja tidak benar, bisa melampiaskan malapetaka disistem komputer. Masalah-masalah ini berada di luar lingkup pekerjaan yang dijelaskan oleh Cristian [1989], yang mengasumsikan bahwa sumber sinyal waktu eksternal adalah self-checking. Cristian dan Fetzer [1994] menggambarkan sebuah keluarga protokol probabilistik untuk clock internal sinkronisasi, yang masing-masing mentolerir kegagalan tertentu. Srikanth dan Toueg [1987] pertama kali dijelaskan algoritma yang optimal sehubungan dengaN akurasi disinkronkan jam, sementara toleransi beberapa kegagalan. Dolev et al. [1986]  menunjukkan bahwa jika f adalah jumlah jam rusak dari total N, maka kita harus memiliki N> 3f jika yang lain, yang benar, jam masih dapat mencapai kesepakatan. Masalah yang berhubungan dengan ,Jam rusak sebagian ditangani oleh algoritma Berkeley, yang dijelaskan selanjutnya. Masalah gangguan berbahaya dengan sinkronisasi waktu dapat ditangani oleh teknik otentikasi.

3.3  Algoritma Berkeley

Gusella dan ZATTI [1989] menggambarkan sebuah algoritma untuk sinkronisasi internal yang mereka dikembangkan untuk koleksi komputer yang menjalankan Berkeley UNIX. Di dalamnya, coordinator komputer yang dipilih untuk bertindak sebagai master. Tidak seperti dalam protokol Cristian, komputer ini jajak pendapat secara berkala komputer lain yang jam harus disinkronkan, yang disebut budak. Budak mengirim kembali nilai-nilai jam mereka untuk itu. master memperkirakan lokal mereka kali jam dengan mengamati kali pulang-pergi (mirip dengan teknik Cristian), dan rata-rata nilai yang diperoleh (termasuk membaca jam sendiri ini). Saldo probabilitas adalah bahwa rata-rata ini membatalkan kecenderungan jam individu berlari cepat atau lambat. Akurasi protokol tergantung pada nominal waktu maksimum round-trip antara master dan slave. master menghilangkan pembacaan sesekali dikaitkan dengan kali lebih besar dari maksimum ini. Alih-alih mengirim waktu saat ini diperbarui kembali ke komputer lain – yang akan memperkenalkan ketidakpastian lebih lanjut karena waktu transmisi pesan – master mengirimkan jumlah dimana jam setiap individu budak membutuhkan penyesuaian. Ini bisa menjadi nilai positif atau negatif.

Algoritma Berkeley menghilangkan bacaan dari jam rusak. jam seperti bisa memiliki efek samping yang signifikan jika rata-rata biasa diambil jadi bukan master Dibutuhkan rata-rata toleran. Artinya, subset dipilih dari jam yang tidak berbeda dari satu sama lain dengan lebih dari jumlah yang ditentukan, dan rata-rata diambil dari bacaan dari hanya jam ini.

Gusella dan ZATTI menggambarkan sebuah eksperimen yang melibatkan 15 komputer yang jam yang disinkronisasi ke dalam sekitar 20-25 milidetik menggunakan protokol mereka. Lingkungan setempat tarif hanyut jam 'diukur kurang dari 2u10-5, dan maksimum round-trip waktu diambil menjadi 10 milidetik. Harus master gagal, maka lain dapat dipilih untuk mengambil alih dan fungsi persis seperti pendahulunya. Bagian 15.3 membahas beberapa pemilihan umum tujuan algoritma. Perhatikan bahwa ini tidak dijamin untuk memilih master baru dalam waktu dibatasi, sehingga perbedaan antara dua jam akan terbatas jika mereka digunakan.

The Network Time Protocol
Metode Cristian dan algoritma Berkeley dimaksudkan terutama untuk digunakan dalam intranet. Network Time Protocol (NTP) [Mills 1995] mendefinisikan sebuah arsitektur untuk waktu pelayanan dan protokol untuk mendistribusikan informasi waktu melalui Internet.desain kepala

NTP bertujuan dan fitur adalah sebagai berikut:

Untuk memberikan layanan yang memungkinkan klien di Internet yang akan disinkronisasi akurat ke UTC: Meskipun penundaan pesan besar dan variabel yang ditemui di komunikasi internet, NTP menggunakan teknik statistik untuk penyaringan data waktu dan membedakan antara kualitas waktu data dari berbagai



Untuk memberikan layanan handal yang dapat bertahan kerugian panjang konektivitas: Ada adalah server berlebihan dan jalur berlebihan antara server. The bisa server mengkonfigurasi ulang sehingga untuk terus memberikan layanan jika salah satu dari mereka menjadi unreachable. Untuk memungkinkan klien untuk mensinkronisasi cukup sering untuk mengimbangi tingkat drift ditemukan di sebagian besar komputer: Layanan ini dirancang untuk skala jumlah besar dari klien dan server. Untuk memberikan perlindungan terhadap interferensi dengan waktu layanan, apakah berbahaya atau kebetulan: Waktu layanan menggunakan teknik otentikasi untuk memeriksa waktu yang Data berasal dari sumber terpercaya yang diklaim. Hal ini juga memvalidasi alamat kembali pesan yang dikirim ke sana.

Layanan NTP disediakan oleh jaringan server yang berlokasi di Internet. Utama server yang terhubung langsung ke sumber waktu seperti jam radio menerima UTC; server sekunder disinkronkan, akhirnya, dengan server utama. Server terhubung dalam hirarki logis disebut subnet sinkronisasi (Gambar 14.3 Contoh sinkronisasi subnet dalam pelaksanaan NTP Panah-panah menunjukkan kontrol sinkronisasi, angka menunjukkan strata. ), yang kadarnya disebut strata. server utama menempati strata 1: mereka berada di akar.



Strata 2 server adalah server sekunder yang disinkronkan langsung dengan primer server; strata 3 server akan disinkronisasi dengan strata 2 server, dan sebagainya. Itu tingkat terendah (daun) server mengeksekusi dalam workstation pengguna '. Jam milik server dengan nomor strata tinggi bertanggung jawab untuk kurang akurat dibandingkan dengan angka strata rendah, karena kesalahan yang diperkenalkan pada setiap tingkat sinkronisasi.

NTP juga memperhitungkan pesan Total round-trip penundaan ke akar dalam menilai kualitas data ketepatan waktu yang dimiliki oleh server tertentu. Sinkronisasi subnet dapat mengkonfigurasi ulang sebagai server menjadi tidak terjangkau atau kegagalan terjadi. Jika, misalnya, sumber UTC server utama ini gagal, maka dapat menjadi BAGIAN 14.3 Sinkronisasi FISIK JAM 605 strata 2 server sekunder. Jika sumber normal server sekunder untuk sinkronisasi gagal atau menjadi tidak terjangkau, maka mungkin melakukan sinkronisasi dengan server lain.

server NTP sinkronisasi dengan satu sama lain dalam satu dari tiga mode: multicast, rosedur-panggilan dan modus simetris. Modus multicast dimaksudkan untuk digunakan pada kecepatan tinggi LAN. Satu atau lebih server secara berkala multicast waktu untuk server berjalan di komputer lain yang terhubung dengan LAN, yang mengatur jam mereka dengan asumsi penundaan kecil. Mode ini dapat mencapai akurasi hanya relatif rendah, tetapi orang-orang yang tetap berada dianggap cukup untuk berbagai tujuan.

Modus prosedur-panggilan mirip dengan operasi algoritma Cristian, menggambarkan Dalam Bagian 14.3.2. Dalam mode ini, satu server menerima permintaan dari komputer lain, yang memproses dengan membalas dengan timestamp nya (jam saat membaca). Mode ini cocok mana akurasi yang lebih tinggi diperlukan daripada yang bisa dicapai dengan multicast, atau di mana multicast tidak didukung pada perangkat keras. Sebagai contoh, file server pada yang sama atau tetangga LAN yang perlu menyimpan informasi waktu yang akurat untuk file yang mengakses bisa hubungi server lokal dalam mode prosedur-panggilan. Akhirnya, modus simetris dimaksudkan untuk digunakan oleh server yang menyediakan waktu

Informasi di LAN dan oleh tingkat yang lebih tinggi (strata yang lebih rendah) dari sinkronisasi subnet, dimana akurasi tertinggi yang akan dicapai. Sepasang server yang beroperasi di bertukar pesan modus simetris bantalan informasi waktu. Waktu data dipertahankan sebagai bagian dari hubungan antara server yang dipertahankan untuk meningkatkan akurasi sinkronisasi mereka dari waktu ke waktu. Dalam semua mode, pesan yang disampaikan unreliably, menggunakan standar UDP Internet transportasi protokol. Dalam modus prosedur-panggilan dan modus simetris, proses pertukaran pasang pesan. Setiap pesan dikenakan cap waktu peristiwa pesan baru: local kali ketika pesan NTP sebelumnya antara pasangan itu dikirim dan diterima, dan waktu setempat ketika pesan saat ditransmisikan. Penerima pesan NTP mencatat waktu setempat ketika menerima pesan. Empat kali

Ti - 3, Ti - 2, Ti – 1

Ti Ti-2 Ti-1 Ti-3 Server B Server A

Waktu m m ' Waktu   untuk pesan m dan m 'yang dikirim antara server A dan B. Perhatikan bahwa dalam mode simetris, tidak seperti di algoritma Cristian ini, bisa ada nonnegligible menunda antara kedatangan satu pesan dan pengiriman berikutnya. Juga, pesan mungkin hilang, tapi tiga cap dilakukan oleh setiap pesan yang tetap sah.

Untuk setiap pasangan pesan yang dikirim antara dua server NTP menghitung offset oi, yang merupakan perkiraan yang sebenarnya offset antara dua jam, dan penundaan di, yang merupakan waktu transmisi total untuk dua pesan. Jika benar offset jam di B relatif terhadap yang di A adalah o, dan jika transmisi kali sebenarnya untuk m dan m 'adalah t dan

t ', masing-masing, maka kita harus:

Ti - 2 ti - 3 = + + t o dan ti ti - 1 = + tc - o

Hal ini menyebabkan:

di t t + c Ti - 2 Ti - 3 - Ti Ti - 1 = = + -

dan:

o oi = +? tc - t e 2, di mana oi Ti - 2 Ti - 3 - Ti - 1 + Ti =? - E 2

Menggunakan fakta bahwa t t? c t 0, dapat ditunjukkan bahwa oi di - e 2 o oi di d d + e 2. Jadi oi adalah perkiraan offset, dan di adalah ukuran dari akurasi perkiraan ini. server NTP menerapkan algoritma penyaringan data untuk pasang berturut <oi d? saya >, Yang memperkirakan offset o dan menghitung kualitas perkiraan ini sebagai jumlah statistic disebut dispersi filter. Sebuah dispersi Filter relatif tinggi merupakan relative Data tidak dapat diandalkan. Delapan pasang terbaru <oi d? saya > Dipertahankan.

Seperti Cristian algoritma, nilai oj yang sesuai dengan dj nilai minimum dipilih untuk memperkirakan Hai. Nilai offset yang berasal dari komunikasi dengan sumber tunggal tidak tentu digunakan dengan sendirinya untuk mengontrol jam lokal, namun. Secara umum, server NTP terlibat dalam pertukaran pesan dengan beberapa rekan-rekan. Selain data penyaringan diterapkan untuk pertukaran dengan setiap rekan tunggal, NTP menerapkan algoritma peer-seleksi. Ini mempelajari nilai-nilai yang diperoleh dari pertukaran dengan masing-masing beberapa rekan-rekan, mencari nilai-nilai yang relatif tidak bisa diandalkan. Output dari algoritma ini dapat menyebabkan server untuk mengubah rekan yang terutama menggunakan untuk sinkronisasi. Peers dengan nomor lapisan bawah yang lebih diunggulkan daripada di strata yang lebih tinggi karena mereka adalah 'lebih dekat' dengan sumber waktu utama. Juga, mereka yang terendah dispersi sinkronisasi relatif disukai.

Ini adalah jumlah filter dispersi diukur antara server dan akar subnet sinkronisasi. (Peers bertukar dispersi sinkronisasi dalam pesan, sehingga jumlah ini menjadi dihitung.) NTP mempekerjakan kunci fase Model lingkaran [Mills 1995], yang memodifikasi local frekuensi update jam itu sesuai dengan pengamatan dari tingkat drift. Untuk mengambil Contoh sederhana, jika jam ditemukan selalu mengulur waktu pada tingkat, katakanlah, empat detik per jam, maka frekuensi dapat dikurangi sedikit (dalam perangkat lunak atau perangkat keras) untuk mengkompensasi hal ini. drift jam dalam interval antara sinkronisasi dengan demikian berkurang. Mills mengutip akurasi sinkronisasi pada urutan puluhan milidetik lebih jalur internet, dan satu milidetik pada LAN.





Logical time and logical clocks
Dari sudut pandang setiap proses tunggal, peristiwa yang diperintahkan unik dengan kali ditampilkan pada jam lokal. Namun, seperti Lamport [1978] menunjukkan, karena kita tidak bisa menyinkronkan jam dengan sempurna di sistem terdistribusi, kita tidak bisa dalam penggunaan umum waktu fisik untuk mengetahui urutan dari setiap pasangan yang sewenang-wenang dari peristiwa yang terjadi di dalamnya. Secara umum, kita dapat menggunakan skema yang mirip dengan kausalitas fisik tetapi yang berlaku dalam sistem terdistribusi untuk memesan beberapa peristiwa yang terjadi di proses yang berbeda. Ini memesan didasarkan pada dua titik sederhana dan intuitif jelas:

Jika dua peristiwa terjadi pada proses pi yang sama? i = 1 2 ?? ? } N, maka mereka
terjadi di urutan pi mengamati mereka - ini adalah urutan oi yang kita

didefinisikan di atas.

Setiap kali pesan dikirim antara proses, acara pengiriman pesan terjadi sebelum acara menerima pesan.
Lamport disebut urutan parsial diperoleh generalisasi dua hubungan ini yang terjadi-sebelum hubungan. Hal ini juga kadang-kadang dikenal sebagai hubungan kausal pemesanan atau potensi kausal memesan. Kita dapat mendefinisikan hubungan terjadi-sebelumnya, dilambangkan dengan o, sebagai berikut:

HB1:? Jika proses pi: e oi e ', maka e e o c.

HB2: Untuk setiap pesan m, mengirim (m) o menerima (m)

- Di mana send (m) adalah event pengiriman pesan, dan menerima (m) adalah acara menerima itu.

HB3: Jika e, ec dan es adalah peristiwa sehingga e e o c dan ec o es, maka e e o s.

Jadi, jika e dan ec adalah peristiwa, dan jika e e o c, maka kita dapat menemukan serangkaian acara e1 e2} en ??? terjadi pada satu atau lebih proses sehingga e e1 = dan ec en =, dan untuk i = baik H 1 2? ? }? N - 1 B1 atau HB2 berlaku antara ei dan ei + 1

- Artinya, baik mereka terjadi dalam suksesi pada proses yang sama, atau ada m pesan sehingga ei = kirim (m) dan ei + 1 = menerima (m). Urutan kejadian e1 e2} en ??? tidak perlu unik. Hubungan o diilustrasikan untuk kasus tiga proses, p1, p2 dan p3, diGambar 14.5 Kegiatan yang terjadi di tiga proses p1 p2 p3 b c d e f m1 m2 Fisik waktu.  Hal ini dapat dilihat bahwa o b, sejak peristiwa terjadi dalam urutan ini pada proses p1 (A oi b), dan juga c o d. Selanjutnya, b o c, karena peristiwa ini pengiriman dan

Penerimaan pesan m1, dan juga d o f. Menggabungkan hubungan ini, kita mungkin juga mengatakan bahwa, misalnya, o f. Hal ini juga dapat dilihat dari Gambar 14.5 bahwa tidak semua peristiwa terkait dengan relasi Hai.

Sebagai contoh, e o / dan e a o /, karena mereka terjadi pada proses yang berbeda, dan ada tidak ada rantai pesan intervensi antara mereka. Kami mengatakan bahwa acara seperti dan e yang tidak diperintahkan oleh o yang bersamaan dan menulis ini a-- e __.

Hubungan o menangkap aliran data intervensi antara dua peristiwa. Catatan, Namun, yang dalam data prinsipnya dapat mengalir dengan cara lain selain dengan pesan lewat. Untuk Misalnya, jika Smith memasuki perintah untuk proses untuk mengirim pesan, maka telepon Jones, yang memerintahkan proses nya untuk mengeluarkan pesan lain, penerbitan pertama pesan jelas terjadi-sebelum itu kedua. Sayangnya, karena tidak ada jaringan pesan yang dikirim antara proses penerbitan, kita tidak bisa model jenis ini hubungan dalam sistem kami.

Hal lain yang perlu diperhatikan adalah bahwa jika terjadi-sebelum hubungan memegang antara dua peristiwa, maka kekuatan pertama atau mungkin tidak benar-benar menyebabkan kedua. Sebagai contoh, jika server menerima pesan permintaan dan kemudian mengirimkan balasan, maka jelas balasan transmisi disebabkan oleh transmisi permintaan. Namun, hubungan o hanya menangkap potensi kausalitas, dan dua peristiwa dapat berhubungan dengan o meskipun ada ada hubungan nyata antara mereka. Sebuah proses mungkin, misalnya, menerima pesan dan kemudian mengeluarkan pesan lain, tapi satu yang mengeluarkan setiap lima menit tetap dan bahwa beruang tidak ada hubungannya khusus untuk pesan pertama. Tidak ada kausalitas yang sebenarnya memiliki pernah terlibat, tetapi hubungan o akan memesan peristiwa ini. jam logis • Lamport [1978] menemukan mekanisme sederhana dimana happenedbefore yang pemesanan dapat ditangkap secara numerik, yang disebut jam logis. Sebuah Lamport logis

Jam adalah monoton meningkat kontra software, yang nilainya perlu menanggung ada hubungan tertentu untuk setiap jam fisik. Setiap pi proses terus logis sendiri Jam, Li, yang digunakan untuk menerapkan apa yang disebut Lamport cap waktu untuk acara. Kami menyatakan timestamp acara e di pi oleh Li ? e, dan oleh L e? kita menunjukkan timestamp dari event e pada proses apa pun itu terjadi pada. Untuk menangkap terjadi-sebelum hubungan o, proses memperbarui jam logis mereka dan mengirimkan nilai-nilai jam logis mereka dalam pesan sebagai berikut:

LC1: Li bertambah sebelum setiap acara diterbitkan pada proses pi:

Li: = Li + 1.

LC2: (a) Ketika proses pi mengirim pesan m, itu piggybacks pada m nilai  t Li =.

(b) Pada menerima (m, t), proses pj menghitung Lj: = max Lj? ? t dan kemudian berlaku LC1 sebelum timestamping acara menerima (m).

Meskipun kami kenaikan jam oleh 1, kita bisa memilih setiap nilai positif. Bisa mudah ditampilkan, dengan induksi pada panjang setiap urutan kejadian yang berkaitan dua Peristiwa e dan ec, bahwa e e o c ?? L e? ? L e? c.

Perhatikan bahwa sebaliknya tidak benar. Jika L e? ? L e? c, maka kita tidak bisa menyimpulkan bahwa e e o c. Pada Gambar 14.6 kita menggambarkan penggunaan jam logis untuk contoh yang diberikan di Gambar 14.5. Setiap proses p1, p2 dan p3 telah Jam logis diinisialisasi ke 0. Nilai Jam diberikan adalah mereka segera setelah acara yang mereka berdekatan. Perhatikan bahwa, misalnya, L b? ! L e? tapi b e __.

Benar-benar memerintahkan jam logis ,Beberapa pasang peristiwa yang berbeda,  dihasilkan oleh berbagai proses, memiliki cap waktu Lamport numerik identik. Namun, kita dapat membuat total order pada set peristiwa - yaitu, satu untuk yang semua pasangan peristiwa yang berbeda yang memerintahkan - dengan memperhatikan pengidentifikasi proses di mana peristiwa terjadi. Jika e adalah peristiwa yang terjadi di pi dengan timestamp lokal Ti , Dan ec adalah peristiwa yang terjadi di pj dengan timestamp lokal Tj, kita mendefinisikan cap waktu logis global untuk peristiwa ini ke menjadi Ti? ? i dan Tj? ? j, masing-masing. Dan kita mendefinisikan Ti? ? i Tj? ? ? j jika dan hanya jika baik Ti Tj? , Atau Ti Tj = dan saya j? . pemesanan ini tidak memiliki arti fisik umum (Karena proses pengidentifikasi yang sewenang-wenang), tetapi kadang-kadang berguna. Lamport menggunakannya, misalnya, untuk memesan masuknya proses ke bagian kritis.

jam vektor • Mattern [1989] dan Fidge [1991] dikembangkan jam vektor untuk mengatasi kelemahan dari jam Lamport ini: fakta bahwa dari L e? ? L e? c kita tidak bisa menyimpulkan bahwa e ec · O. Sebuah jam vektor untuk sistem proses N adalah array dari N bilangan bulat. Setiap proses membuat jam sendiri vektor, Vi, yang digunakan untuk timestamp local peristiwa. Seperti cap waktu Lamport, proses dukung-dukungan cap waktu vektor pada pesan yang mereka kirim satu sama lain, dan ada aturan sederhana untuk memperbarui jam:

VC1: Awalnya, Vi > @j =, Untuk 0 i j? =. 1 2? ? } N

VC2: Tepat sebelum pi timestamps sebuah acara, ia menetapkan Vi > @i: = Vi > @i + 1.

VC3: pi termasuk nilai t Vi = di setiap pesan yang dikirimkannya.

VC4: Ketika pi menerima t timestamp dalam sebuah pesan, ia menetapkan Vi

> @j: = Max Vi? > @j? t j> @, untuk = j. Ta 1 2? ? } N raja componentwise yang

maksimal dua cap waktu vektor dengan cara ini dikenal sebagai penggabungan operasi.

Untuk jam vektor Vi, Vi > @i Adalah jumlah peristiwa yang pi telah timestamped, dan Vi> @j Ji? z adalah jumlah peristiwa yang telah terjadi di pj yang memiliki potensial pi terpengaruh. (Proses pj mungkin telah timestamped peristiwa lainnya saat ini, tapi tidak adainformasi telah mengalir ke pi tentang mereka dalam pesan yang belum.)

Kita bisa membandingkan cap waktu vektor sebagai berikut:



V V = = untuk c IFF V j> @ Vc> @j j = 1 2……N

V V d c IFF V j> @ d Vc> @j untuk j = 1 2…… N

V V? c IFF V V d c ?? V V z c

Mari V e? menjadi timestamp vektor diterapkan oleh proses di mana e terjadi. Ini mudah untuk menunjukkan, dengan induksi pada panjang setiap urutan kejadian yang berkaitan dua peristiwa e dan ec, bahwa e e o c ?? Ve? ? Ve? c. Latihan 10.13 menuntun pembaca untuk menunjukkan sebaliknya: jika V e? ? Ve? c, maka e e o c. Gambar 14.7 menunjukkan cap waktu vektor peristiwa angka 14,5. Hal ini dapat dilihat, misalnya, bahwa V a? ? V f? , Yang mencerminkan fakta bahwa o f. Demikian pula, kita dapat mengetahui bahwa dua peristiwa yang bersamaan dengan membandingkan cap waktu mereka. Sebagai contoh, yang c e __ dapat dilihat dari fakta bahwa baik V c? d V e? atau V e? d V c? . cap vektor memiliki kelemahan, dibandingkan dengan Lamport cap waktu, dari mengambil jumlah penyimpanan dan payload pesan yang sebanding dengan N, jumlah proses. Charron-Bost [1991] menunjukkan bahwa, jika kita dapat memberitahu apakah dua peristiwa yang bersamaan dengan memeriksa cap waktu mereka, maka Dimensi N tidak dapat dihindari. Namun, teknik yang ada untuk menyimpan dan mengirimkan jumlah data yang lebih kecil, dengan mengorbankan proses yang diperlukan untuk merek konstruksi vektor lengkap. Raynal dan Singhal [1996] memberikan penjelasan tentang beberapa ini teknik. Mereka juga menggambarkan gagasan jam matriks, dimana proses tetap perkiraan proses lainnya 'vector kali serta mereka sendiri. 14,5 negara global





Global states


Pada bagian berikutnya ini dan kita memeriksa masalah mencari tahu apakah tertentu Properti adalah benar dari sistem terdistribusi sebagai dijalankan. Kita mulai dengan memberikan contoh-contoh pengumpulan didistribusikan sampah, deteksi deadlock, deteksi pemutusan dan debugging:





Pengumpulan sampah didistribusikan: Sebuah benda dianggap sampah jika tidak ada lagi referensi untuk itu di mana saja di sistem terdistribusi. memori diambil oleh objek yang dapat direklamasi setelah diketahui sampah. Untuk memeriksa bahwa objek adalah sampah, kita harus memastikan bahwa tidak ada referensi untuk itu di mana saja di sistem. Pada Gambar 14.8 (a), proses p1 memiliki dua benda yang keduanya memiliki referensi – satu memiliki referensi dalam p1 itu sendiri, dan p2 memiliki referensi yang lain. Proses p2 memiliki satu objek sampah, dengan tidak ada referensi untuk itu di mana saja di sistem. Ia juga memiliki objek yang tidak p1 atau p2 memiliki referensi, tapi ada referensi untuk itu dalam

pesan yang dalam perjalanan antara proses. Hal ini menunjukkan bahwa ketika kita mempertimbangkan Sifat dari suatu sistem, kita harus menyertakan keadaan saluran komunikasi serta sebagai keadaan proses. Gambar 14.8 Mendeteksi properti global yang p1 p2 pesan objek sampah obyek referensi (A) Pengumpulan sampah p p2 1 menunggu-untuk menunggu-untuk (b) Deadlock p p2 1 mengaktifkan pasif pasif (c) Penghentian deteksi kebuntuan didistribusikan Sebuah kebuntuan didistribusikan terjadi ketika masing-masing dari kumpulan proses menunggu proses lain untuk mengirim pesan, dan mana ada siklus dalam grafik ini 'menunggu-untuk' hubungan. Gambar 14.8 (b) menunjukkan bahwa proses p1 dan p2 masing-masing menunggu pesan dari yang lain, sehingga sistem ini tidak akan membuat kemajuan. Deteksi pemutusan didistribusikan:

Masalahnya di sini adalah bagaimana mendeteksi bahwa algoritma terdistribusi telah dihentikan. Mendeteksi terminasi adalah masalah yang terdengar menipu mudah untuk memecahkan: tampaknya pada awalnya hanya diperlukan untuk menguji apakah setiap proses  telah dihentikan. Untuk melihat bahwa ini tidak begitu, pertimbangkan algoritma didistribusikan dieksekusi oleh dua proses p1 dan p2, yang masing-masing dapat meminta nilai-nilai dari yang lain. Instan, kita dapat menemukan bahwa proses ini baik aktif atau pasif – pasif Proses tidak terlibat dalam setiap kegiatan sendiri tetapi siap untuk menanggapi dengan nilai yang diminta oleh yang lain. Misalkan kita menemukan bahwa p1 adalah pasif dan p2 adalah pasif (Gambar 14.8c). Untuk melihat bahwa kita mungkin tidak menyimpulkan bahwa algoritma memilik  dihentikan, pertimbangkan skenario berikut: ketika kita diuji p1 untuk pasif, sebuah pesan sedang dalam perjalanan dari p2, yang menjadi pasif segera setelah mengirim saya t. Pada saat menerima pesan, p1 menjadi aktif kembali - setelah kami telah menemukan itu menjadi pasif. algoritma tidak dihentikan.

Fenomena pemutusan dan kebuntuan serupa dalam beberapa hal, tetapi mereka adalah masalah yang berbeda. Pertama, kebuntuan dapat mempengaruhi hanya sebagian dari proses di sistem, sedangkan semua proses harus dihentikan. Kedua, proses pasif adalah tidak sama dengan menunggu dalam siklus deadlock: proses buntu mencoba untuk melakukan tindakan lebih lanjut, yang proses lain menunggu; proses pasif tidak terlibat dalam aktivitas apapun. Didistribusikan debugging: didistribusikan sistem yang kompleks untuk debug [Bonnaire et al. 1995], dan perawatan harus diambil dalam membangun apa yang terjadi selama eksekusi. Misalnya, anggaplah Smith telah menulis sebuah aplikasi di mana setiap proses pi mengandung variabel xi (i =). Variabel chan 1 2? ? } N ge sebagai program mengeksekusi, tapi mereka diwajibkan selalu berada dalam nilai G dari satu sama lain. Sayangnya, ada bug dalam program, dan Smith menduga bahwa di bawah tertentu keadaan xi xj -! G untuk beberapa i dan j, melanggar kendala konsistensinya. Nya

Masalahnya adalah bahwa hubungan ini harus dievaluasi untuk nilai-nilai variabel yang terjadi pada saat yang sama. Setiap masalah di atas memiliki solusi tertentu yang disesuaikan untuk itu; tetapi mereka semua menggambarkan perlu mengamati keadaan global, dan memotivasi pendekatan umum.

negara global dan pemotongan yang konsisten
Hal ini dimungkinkan pada prinsipnya untuk mengamati suksesi negara dari proses individu, tetapi pertanyaan tentang bagaimana untuk memastikan keadaan global sistem - keadaan koleksi proses - jauh lebih sulit untuk mengatasi. Masalah penting adalah tidak adanya waktu global. Jika semua proses telah sempurna jam disinkronisasi, maka kita bisa menyepakati waktu di mana setiap proses akan merekam keadaan - hasilnya akan menjadi negara global yang sebenarnya dari sistem. Dari koleksi Proses menyatakan kita bisa mengatakan, misalnya, apakah proses menemui jalan buntu. Tapi kita tidak dapat mencapai sinkronisasi jam yang sempurna, sehingga metode ini tidak tersedia bagi kita. Jadi kita mungkin bertanya apakah kita bisa merakit sebuah negara global yang berarti dari local negara tercatat pada waktu yang berbeda nyata. Jawabannya adalah yang memenuhi syarat 'ya', tetapi untuk melihat ini pertama-tama kita harus memperkenalkan beberapa definisi.

Mari kita kembali ke sistem umum kami ?? N proses pi (i =), yang 1 2 …..} N eksekusi kita ingin belajar. Kami mengatakan di atas bahwa serangkaian peristiwa terjadi pada setiap proses, dan bahwa kita dapat mencirikan pelaksanaan setiap proses sejarahnya:

sejarah (pi hi <ei 0 ei 1 ei 2 = = ……. }>

Demikian pula, kita dapat mempertimbangkan awalan terbatas sejarah proses ini:

Hai k<ei 0 ei 1} ei k =…. >

Setiap acara baik adalah tindakan internal proses (misalnya, memperbarui satu variabel nya), atau pengiriman atau penerimaan pesan atas komunikasi saluran yang menghubungkan proses. Pada prinsipnya, kita dapat merekam apa yang terjadi dalam pelaksanaan ?? 's. Setiap proses dapaT merekam peristiwa yang terjadi di sana, dan suksesi negara melewati. Kami dilambangkan dengan sik keadaan proses pi segera sebelum acara k terjadi, sehingga si yang  0 adalah keadaan awal dari pi. Kami mencatat pada contoh di atas bahwa keadaan saluran komunikasi kadang-kadang relevan. Daripada memperkenalkan tipe baru negara, kita membuat proses merekam pengiriman atau penerimaan semua pesan sebagai bagian dari mereka negara. Jika kami menemukan bahwa proses pi telah mencatat bahwa itu mengirim pesan m untuk memproses pj ? i j z, maka dengan memeriksa apakah pj telah menerima pesan kita dapat menyimpulkan apakah atau tidak m adalah bagian dari negara bagian saluran antara pi dan pj. Kami juga dapat membentuk sejarah global ?? sebagai kesatuan proses individual

sejarah: H h0 h1} h ……. N - 1 =

Secara matematis, kita dapat mengambil set negara dari proses individu untuk membentuk globalnegara S s1 s2} sN =. ? ? ? Tapi yang negara global bermakna - yaitu, yang negara proses bisa terjadi pada saat yang sama? Sebuah negara global sesuai dengan paraf prefiks dari sejarah proses individu. Sebuah memotong eksekusi sistem adalah subset sejarah global yang merupakan gabungan dari prefiks dari sejarah proses:

C h1 c1 h2 c2} Hn c ………N =

si negara dalam S kondisi global yang sesuai dengan cut C adalah bahwa pi segera setelah acara terakhir diproses oleh pi di cut – ei ci (i =). Set peristiwa 1 2 …. } N {ei ci: i =} disebut 1 2….. } N perbatasan dipotong. Mempertimbangkan peristiwa yang terjadi di proses p1 dan p2 ditunjukkan pada Gambar 14.9Cut m1 m2 p1 p2 fisik waktu e 1 0 cut konsisten e 1 1 e 1 2 e 1 3 e 2 0 e 2 1 e 2 2 Itu Angka menunjukkan dua luka, satu dengan perbatasan <e1 0 e2 0? > Dan lain dengan perbatasan <e1 2 e2 2? >.

Pemotongan paling kiri tidak konsisten. Hal ini karena pada p2 itu termasuk penerimaan m1 pesan, tetapi pada p1 tidak termasuk pengiriman pesan itu. Hal ini menunjukkan sebuah 'efek' tanpa 'sebab'. Eksekusi yang sebenarnya tidak pernah dalam keadaan global yang sesuai dengan negara proses di perbatasan itu, dan kami dapat pada prinsipnya mengatakan ini dengan memeriksa orelation antara peristiwa. Sebaliknya, dipotong paling kanan konsisten Ini mencakup baik pengiriman dan penerimaan pesan m1 dan pengiriman tetapi tidak penerimaan pesan m2. Yang konsisten dengan eksekusi yang sebenarnya - setelah semua, Pesan mengambil beberapa waktu untuk tiba. Pemotongan C konsisten jika, untuk setiap acara mengandung, juga berisi semua peristiwa yang terjadi-sebelum acara yang:

Untuk semua acara e .. C, f.. e .. f.. C

Sebuah negara global yang konsisten adalah salah satu yang sesuai dengan potongan yang konsisten. Kita boleh mencirikan pelaksanaan sistem terdistribusi sebagai rangkaian transisi antara negara global sistem:

S0 S1 S2 ……..

Dalam setiap transisi, tepatnya satu peristiwa terjadi pada beberapa proses tunggal dalam sistem. Ini peristiwa baik pengiriman pesan, penerimaan pesan atau acara internal. Jika dua peristiwa yang terjadi secara bersamaan, kita tetap bisa anggap mereka telah terjadi dalam urutan yang pasti - katakanlah, memerintahkan menurut pengidentifikasi proses. (Peristiwa yang terjadi bersamaan harus bersamaan. tidak terjadi-sebelum yang lain) sistem A berkembang dengan cara ini melalui negara global yang konsisten. Sebuah menjalankan adalah memesan total semua peristiwa dalam sejarah global yang konsisten dengan memesan setiap sejarah lokal, 0i 0i = 102….. N0. Sebuah linearisasi atau konsisten dijalankan adalah suatu urutan dari peristiwa dalam sejarah global yang konsisten dengan ini terjadi-sebelumSehubungan…..on H.

negara predikat global, stabilitas, keamanan dan liveness
Mendeteksi kondisi seperti deadlock atau penghentian jumlah untuk mengevaluasi global negara predikat. Sebuah predikat negara global adalah fungsi yang memetakan dari set global negara dari proses dalam sistem to {Benar, Salah}. Salah satu karakteristik yang berguna dari predikat terkait dengan keadaan suatu objek menjadi sampah, sistem menjadi buntu atau sistem yang dihentikan adalah bahwa mereka semua stabil: setelah sistem memasuki keadaan di mana predikat Benar, itu tetap benar di semua negara di masa depan dapat dicapai dari negara itu. Sebaliknya, ketika kita memantau atau debug aplikasi kita sering tertarik predikat non-sta seperti yang di contoh kita variabel yang Perbedaan seharusnya dibatasi. Bahkan jika aplikasi mencapai keadaan di mana memperoleh terikat, itu tidak perlu tinggal di negara itu. Kami juga dicatat di sini dua gagasan lanjut relevan dengan predikat negara global

The ‘snapshot’ algorithm of Chandy and Lamport
Chandy dan Lamport [1985] menggambarkan 'snapshot' algoritma untuk menentukan global yang negara dari sistem terdistribusi, yang sekarang kita hadir. Tujuan dari algoritma ini adalah untuk merekam satu set proses dan saluran negara (a 'snapshot') untuk serangkaian proses pi (I = 1..2… N) seperti itu, meskipun kombinasi negara tercatat mungkin tidak pernah telah terjadi pada saat yang sama, negara global yang tercatat konsisten. Kita akan melihat bahwa negara bahwa catatan algoritma snapshot memiliki nyaman properti untuk mengevaluasi predikat global yang stabil. Catatan algoritma negara lokal di proses; tidak memberikan metode untuk mengumpulkan negara global di satu lokasi. Sebuah metode yang jelas untuk mengumpulkan negara adalah untuk semua proses untuk mengirim negara mereka direkam ke proses kolektor yang ditunjuk, tapi kami akan tidak membahas masalah ini lebih lanjut di sini.

Algoritma ini mengasumsikan bahwa:

Baik saluran atau proses gagal - komunikasi yang handal sehingga setiap pesan terkirim akhirnya diterima utuh, tepat sekali.
Saluran yang searah dan menyediakan pengiriman pesan FIFO-memerintahkan.
Grafik proses dan saluran sangat terhubung (ada jalur antara dua proses).
Setiap proses dapat memulai snapshot global yang setiap saat.
Proses dapat melanjutkan eksekusi mereka dan mengirim dan menerima yang normal
pesan saat snapshot berlangsung.

Untuk setiap pi proses, biarkan saluran masuk menjadi orang-orang di pi dimana proses lainnya kirimkan pesan; sama, saluran keluar dari pi adalah mereka yang menjadi mengirimkan pesan ke proses lainnya. Ide penting dari algoritma ini adalah sebagai berikut. Setiap Proses mencatat negara dan juga, untuk setiap saluran masuk, satu set pesan yang dikirim ke saya  Catatan proses, untuk setiap saluran, setiap pesan yang tiba setelah mencatat nya negara dan sebelum pengirim mencatat negara sendiri. Pengaturan ini memungkinkan kita untuk merekam negara dari proses pada waktu yang berbeda tetapi untuk account untuk perbedaan antara negara proses dalam hal pesan ditransmisikan tetapi belum diterima. Jika proses pi memiliki mengirim m pesan untuk memproses pj, tapi pj belum menerimanya, maka kita memperhitungkan m sebagai milik negara saluran antara mereka. algoritma berlangsung melalui penggunaan pesan penanda khusus, yang berbeda dari pesan lain proses mengirim dan yang proses dapat mengirimkan dan terima saat mereka melanjutkan dengan eksekusi normal mereka. penanda memiliki peran ganda: sebagai prompt untuk penerima untuk menyelamatkan negara sendiri, jika belum melakukannya; dan sebagai berarti menentukan pesan mana yang termasuk di negara channel. Algoritma ini didefinisikan melalui dua aturan, penanda menerima aturan dan penanda mengirim aturan (Gambar 14.10). Penanda mengirim aturan mewajibkan proses untuk mengirim penanda setelah mereka telah mencatat negara mereka, tapi sebelum mereka mengirim pesan lainnya. Penanda menerima aturan mewajibkan proses yang tidak tercatat negara untuk melakukan begitu. Dalam hal ini, ini adalah penanda pertama yang telah diterima. Ini catatan yang pesan kemudian tiba di saluran masuk lainnya.

Beberapa proses dapat memulai merekam secara bersamaan dengan cara ini (selama penanda

mereka menggunakan dapat dibedakan).

Proses p1 mencatat negara dalam sebenarnya negara global S0, ketika keadaan p1 adalah <$ 1000, 0>. Setelah penanda mengirimkan aturan, proses p1 kemudian memancarkan pesan penanda atas nya outgoing channel c2 sebelum mengirim pesan aplikasi-tingkat berikutnya: (Order 10, $ 100), melalui saluran c2. sistem memasuki sebenarnya S1 negara global. Sebelum p2 menerima penanda, memancarkan pesan aplikasi (lima widget) lebih c1 dalam menanggapi order sebelumnya p1 's, menghasilkan sebenarnya S2 negara global baru. Sekarang proses p1 menerima pesan p2 's (lima widget), dan p2 menerima penanda. Setelah penanda menerima aturan, p2 mencatat negara sebagai <$ 50, 1995> dan bahwa saluran c2 sebagai urutan kosong. Mengikuti aturan penanda pengiriman, ia akan mengirimkan Pesan penanda lebih c1. Ketika proses p1 menerima pesan penanda p2 's, itu mencatat keadaan saluran c1 sebagai pesan tunggal (lima widget) yang diterima setelah pertama kali tercatat keadaan.

The negara global akhir yang sebenarnya adalah S3.

Mencatat negara terakhir adalah p1: <$ 1000, 0>; p2: <$ 50, 1995>; c1: <(lima

widget)>; c2: <>. Perhatikan bahwa negara ini berbeda dari semua negara global melalui mana

sistem benar-benar berlalu.

Kami lebih lanjut dapat membangun hubungan reachability antara negara global yang diamati dan awal dan akhir negara global ketika algoritma berjalan. Mari Sys e0 e1 = menjadi linierisasi sistem seperti itu dijalankan (di mana dua peristiwa terjadi tepat pada saat yang sama, kita memesan mereka sesuai dengan pengidentifikasi proses). Biarkan Sinit menjadi negara global segera sebelum proses pertama yang tercatat negaranya; biarkan Sfinal menjadi negara global saat algoritma snapshot berakhir, segera setelah tindakan negara-rekaman terakhir; dan biarkan Ssnap menjadi negara global yang tercatat. Kita akan menemukan permutasi dari Sys, Sys e 0 e 1 e 2 = sehingga semua tiga Negara Sinit, Ssnap dan Final terjadi di Sys, Ssnap dicapai dari Sinit di Sys, dan Sfinal dicapai dari Ssnap di Sys. Gambar 14.13 menunjukkan situasi ini, di mana atas linierisasi adalah Sys dan linierisasi rendah Sys Reachability milik algoritma snapshot berguna untuk mendeteksi predikat stabil. Secara umum, setiap non-stabil predikat kita membangun sebagai Benar di negara bagian Ssnap mungkin atau mungkin belum Benar dalam pelaksanaan aktual yang kondisi global kami mencatat. Namun, jika predikat stabil

Benar di negara bagian Ssnap maka kita dapat menyimpulkan bahwa predikat adalah benar dalam keadaan Final, scene dengan definisi predikat stabil yang Benar dari negara S juga benar dari setiap Negara dicapai dari S. Demikian pula, jika predikat mengevaluasi ke False untuk Ssnap, maka harus juga menjadi False untuk Sinit.

Distributed debugging
Kami sekarang meneliti masalah merekam sistem negara global sehingga kita dapat membuat pernyataan yang berguna tentang apakah negara sementara - yang bertentangan dengan keadaan yang stabil - terjadi dalam eksekusi yang sebenarnya. Ini adalah apa yang kita butuhkan, pada umumnya, ketika debugging sistem terdistribusi. Kami memberi contoh di atas di mana masing-masing satu set proses pi memiliki variabel xi. Kondisi keamanan yang diperlukan dalam contoh ini adalah xi - xj (I j = 1 2 N); kendala ini harus dipenuhi meskipun proses dapat mengubah nilai variabel setiap saat. Contoh lain adalah sistem terdistribusi mengendalikan Sistem pipa di sebuah pabrik di mana kita tertarik apakah semua katup (dikendalikan oleh proses yang berbeda) yang terbuka pada beberapa waktu. Dalam contoh ini, kita tidak bisa secara umum mengamati nilai-nilai variabel atau negara bagian katup secara bersamaan. Itu tantangan adalah untuk memantau pelaksanaan sistem dari waktu ke waktu - untuk menangkap informasi 'jejak' daripada snapshot tunggal - sehingga kita dapat membangun post hoc apakah diperlukan Kondisi keselamatan adalah atau mungkin telah dilanggar. Chandy dan Lamport ini [1985] algoritma snapshot mengumpulkan negara dala didistribusikan fashion, dan kami menunjukkan bagaimana proses dalam sistem bisa mengirim negara mereka berkumpul untuk proses memantau untuk koleksi. Algoritma kita jelaskan berikutny (karena Marzullo dan Neiger [1991]) adalah terpusat. proses yang diamati mengirimkan negara mereka untuk proses yang disebut monitor, yang merakit negara secara global yang konsisten dari apa menerima. Kami menganggap monitor untuk berada di luar sistem, mengamat pelaksanaannya.

Collecting the state
Mengamati proses pi yang i = 1 2 N mengirim keadaan awal mereka ke monitor awalnya, dan kemudian dari waktu ke waktu, dalam pesan negara. monitor mencatat Pesan negara dari masing-masing pi proses dalam Qi antrian terpisah, untuk setiap i = 1 2 N. Kegiatan mempersiapkan dan mengirim pesan negara dapat menunda normal pelaksanaan proses diamati, tetapi tidak sebaliknya mengganggu itu. Ada tidak perlu mengirim negara kecuali awalnya dan ketika perubahan. Ada dua optimasi untuk mengurangi lalu lintas negara-pesan ke monitor. Pertama, negara global predikat mungkin tergantung hanya pada bagian-bagian tertentu dari negara proses '- misalnya, hanya pada negara-negara variabel tertentu - sehingga proses diamati hanya perlu mengirim negara yang relevan untuk monitor. Kedua, mereka hanya perlu mengirimkan negara mereka pada saat-saat ketika predikat may menjadi Benar atau berhenti menjadi Benar. Tidak ada gunanya dalam mengirimkan perubahan untuk negara yang tidak mempengaruhi nilai predikat.

Observing consistent global states
Monitor harus merakit negara global yang konsisten terhadap yang mengevaluasi . Penarikan bahwa pemotongan C konsisten jika dan hanya jika untuk semua acara e di cut C, f e f C. Sebagai contoh, Gambar 14.14 Vector cap waktu dan nilai-nilai variabel untu pelaksanaan Gambar 14.9 m1 m2 p1 p2 Fisik waktu potong C1 (1,0) (2,0) (4,3) (2,1 (2,2) (2,3 (3,0) x1 = 1 x1 = 100 x1 = 105 x2 = 100 x2 = 95 x2 = 90 x1 = 90 potong C2 Gambar 14.14 menunjukkan dua proses p1 dan p2 dengan variabel x1 dan x2, masing-masing. Peristiwa ditampilkan pada baris waktu (dengan vektor cap waktu) yang penyesuaian terhadap nilai-nilai dari dua variabel. Awalnya, x1 = x2 = 0. Yan dibutuhkan adalah x1 - x2 50. Proses membuat penyesuaian untuk variabel mereka, tapi 'besar' penyesuaian menyebabkan pesan yang berisi nilai baru yang akan dikirim ke proses lainnya. Ketika salah satu dari proses menerima pesan penyesuaian dari yang lain, ia menetapkan nya variabel sama dengan nilai yang terkandung dalam pesan. Setiap kali salah satu proses p1 atau p2 menyesuaikan nilai variabelnya (apakah itu adalah penyesuaian 'kecil' atau 'besar' satu), ia akan mengirimkan nilai dalam pesa negara untuk memonitor. Yang terakhir membuat pesan negara dalam per-proses antrian untuk analisis. Jika Monitor yang menggunakan nilai-nilai dari tidak konsisten cut C1 pada Gambar 14.14 maka akan menemukan bahwa x1 = 1 x2 = 100, melanggar Kendal x1 - x2 50. Tapi keadaan ini urusan tidak pernah terjadi. Di sisi lain, nilai dari konsisten cut C2 acara x1 = 105 x2 = 90. Agar monitor dapat membedakan negara global yang konsisten dari tidak konsisten negara global, proses diamati melampirkan nilai jam vektor mereka dengan negar mereka pesan. Setiap antrian Qi disimpan dalam mengirimkan pesanan, yang dapat segera didirikan dengan memeriksa komponen engan dari cap waktu vektor. Tentu saja, memantau dapat menyimpulkan apa-apa tentang pemesanan negara yang dikirim oleh proses yang berbeda  dari pesanan kedatangan mereka, karena latency pesan variabel. Ini bukan haru memeriksa  cap waktu vektor pesan negara. Mari s1 s2 sN = menjadi negara global yang diambil dari pesan menyatakan bahwa Monitor telah menerima. Mari V si   menjadi timestamp vektor dari negar s diterim  dari pi. Maka dapat ditunjukkan bahwa S adalah keadaan global yang konsisten jika da  hanya jika:





Evaluating possibly
Monitor dapat menemukan set-negara yang konsisten di tingkat L + 1 dijangkau dari keadaan konsisten diberikan di tingkat L dengan metode berikut Membiarkan S s1 s2 sN = menjadi negara yang konsisten. Kemudian keadaa konsisten di tingkat berikutnya  dicapai dari S adalah dalam bentuk S s1 s2 si sN = , yang berbeda dari S hanya dengan mengandung negara berikutnya (setelah peristiwa tunggal) dari beberapa prose pi. monitor dapat menemukan semua negara tersebut dengan melintasi antrian pesan negara Qi (i = 1 2 N). Itu negara S dicapai dari S jika dan hanya jika:  untuk j = 1 2 N, j i: V sj j V si j Kondisi ini berasal dari kondisi CGS atas dan dari fakta bahwa S sudah menjadi negara global yang konsisten. Sebuah negara yang diberikan mungkin pada umumny ditempuh dari beberapa negara di tingkat sebelumnya, sehingga monitor harus berhati-hati untu mengevaluasi konsistensi masing-masing Negara hanya sekali.



Evaluating definitely
Untuk mengevaluasi pasti , monitor lagi melintasi kisi negara dapat dicapai tingkat pada suat waktu, mulai dari keadaan awal s1 0 s2 0 sN 0 . Algoritma (yang ditunjukkan pada Gambar 14.16) lagi mengasumsikan bahwa eksekusi tak terbatas tetapi dapat dengan mudah diadaptasi untuk terbatas eksekusi. Ia memelihara set Serikat, yang berisi negara-negara di tingkat saat ini yang mungkin dicapai pada linierisasi dari keadaan awal dengan melintasi hanya menyatakan untuk yang mengevaluasi ke False. Selama linierisasi seperti itu ada, kita mungkin tidak menegaskan pasti : eksekusi bisa mengambil linierisasi ini, dan akan False di setiap tahap sepanjang itu. Jika kita mencapai tingkat yang tidak linierisasi tersebut ada, kita mungkin menyimpulkan pasti . Gambar 14.17 Mengevaluasi pasti



Summary
Bab ini dimulai dengan menggambarkan pentingnya ketepatan waktu yang akurat untuk didistribusikan sistem. Kemudian dijelaskan algoritma untuk jam sinkronisasi meskipun drift antara mereka dan variabilitas penundaan pesan antar komputer. Tingkat akurasi sinkronisasi yang praktis diperoleh memenuhi banyak persyaratan tapi tetap tidak cukup untuk menentukan urutan sewenang-wenang sepasang peristiwa yang terjadi di komputer yang berbeda. terjadi-sebelum hubunga adalah parsial Agar peristiwa yang mencerminkan aliran informasi antara mereka - dalam proses, atau melalui pesan antar proses. Beberapa algoritma memerlukan peristiwa harus dipesan di terjadi-sebelum pesanan, misalnya, update berturut-turut dibuat untuk salinan yan terpisah dari data.jam Lamport adalah counter yang diperbarui sesuai dengan yang terjadi-sebelu hubungan antara peristiwa. jam vektor adalah perbaikan pada jam Lamport, di bahwa adalah mungkin untuk menentukan dengan memeriksa cap waktu vektor mereka apakah dua peristiwa yang diperintahkan oleh terjadi-sebelum atau bersamaan. Kami memperkenalkan konsep acara, sejarah lokal dan global, pemotongan, lokal dan negara global, berjalan, negara yang konsisten, linearizations (berjalan konsisten) da reachability. SEBUAH negara yang konsisten atau lari adalah salah satu yang sesuai dengan hubungan yang terjadi-sebelumnya. Kami melanjutkan untuk mempertimbangkan masalah merekam keadaan global yang konsiste dengan mengamati pelaksanaan sistem ini. Tujuan kami adalah untuk mengevaluasi predikat pada negara ini.

Sebuah kelas penting dari predikat adalah predikat stabil. Kami dijelaskan snapshot algoritma Chandy dan Lamport, yang menangkap keadaan global yang konsisten dan memungkinkan kita untuk membuat pernyataan tentang apakah predikat stabil memegang dala  pelaksanaan yang sebenarnya. Kami melanjutkan untuk memberikan algoritma Marzullo dan Neiger untuk menurunkan pernyataan tentang apakah predikat diadakan atau mungkin telah diselenggarakan dalam jangka yang sebenarnya. Algoritma ini menggunakan monitor prose untuk mengumpulkan negara. monitor memeriksa cap waktu vektor untuk mengekstrak onsiste negara global, dan membangun dan mengkaji kisi semua negara global yang konsisten. Algoritma ini melibatkan kompleksitas komputasi besar tetapi berharga untuk  pemahaman dan dapat dari beberapa manfaat praktis dalam sistem nyata di mana relat  sedikit Peristiwa mengubah nilai predikat global. Algoritma ini memiliki varian yang lebih efisien dalam sistem sinkron, di mana jam dapat disinkronkan.  Sebuah skema untuk menerapkan di-paling-sekali pengiriman pesan handal menggunakan disinkronisasi jam untuk menolak duplikat pesan. Proses menempatkan nilai jam lokal mereka (a 'Timestamp') di pesan yang mereka kirim. Setiap penerima menyimpan pemberian meja, untuk setiap Proses pengiriman, pesan timestamp terbesar itu telah melihat. Asumsikan bahwa jam yang disinkronisasi ke dalam 100 ms, dan bahwa pesan dapat tiba di paling 50 ms setelah transmisi.

i) Ketika mungkin proses mengabaikan pesan bantalan cap waktu T, jika telah mencatat
pesan terakhir yang diterima dari proses yang sebagai memiliki timestamp T?

ii) Ketika mungkin penerima menghapus cap 175.000 (ms) dari tabel yang? (Petunjuk: gunakan
nilai jam lokal penerima.)

iii) Haruskah jam secara internal disinkronkan atau eksternal disinkronkan?

halaman 601

Seorang klien mencoba untuk melakukan sinkronisasi dengan server waktu. Ini catatan kali pulang-pergi dan Cap waktu dikembalikan oleh server dalam tabel di bawah. Yang kali ini harus ia gunakan untuk mengatur jam-nya? Untuk apa waktu harus itu mengaturnya? Memperkirakan keakuratan pengaturan sehubungan dengan jam server. Jika diketahui bahwa waktu antara pengiriman dan penerimaan pesan dalam sistem yang bersangkutan setidaknya 8 ms, jangan jawaban Anda berubah?





Dua proses P dan Q yang terhubung dalam sebuah cincin menggunakan dua saluran, dan mereka terus-menerus memutar pesan m. Pada satu waktu, hanya ada satu salinan m dalam sistem. Setiap Negara proses terdiri dari jumlah kali itu telah menerima m, dan P mengirimkan m pertama. Di titik tertentu, P memiliki pesan dan negara adalah 101. Segera setelah mengirim m, P memulai algoritma snapshot. Menjelaskan operasi algoritma dalam hal ini, memberikan negara global mungkin (s) dilaporkan oleh itu.