Jam Logis dan Fisik

Jam logis mengurutkan peristiwa berdasarkan kausalitas tanpa mengacu pada waktu nyata, sementara sinkronisasi jam fisik menjaga agar jam waktu nyata mesin yang terpisah tetap berdekatan meskipun ada penyimpangan.

Definition

Jam logis menetapkan stempel waktu bilangan bulat untuk setiap peristiwa yang bersifat monoton di sepanjang setiap proses dan meningkat melintasi komunikasi, menangkap urutan kausal; sinkronisasi jam fisik adalah proses penyesuaian jam perangkat keras mesin sehingga mereka membaca waktu nyata yang kira-kira sama.

Scope

Topik ini mencakup jam logis (skalar) Lamport dan hubungan 'terjadi-sebelum' (happened-before) yang dihormatinya, konstruksi urutan total dari stempel waktu logis, dan sinkronisasi jam fisik—membatasi penyimpangan, bertukar stempel waktu untuk memperkirakan offset, serta algoritma (metode Cristian, algoritma Berkeley, NTP) yang digunakan dalam praktik. Ini membandingkan kapan waktu logis kausal cukup dan kapan waktu nyata benar-benar diperlukan.

Core questions

• Bagaimana stempel waktu dapat ditetapkan sehingga mereka menghormati hubungan kausal 'terjadi-sebelum'?
• Bagaimana urutan total yang konsisten pada peristiwa dibangun dari jam logis?
• Seberapa dekat jam fisik dapat disinkronkan mengingat penundaan jaringan dan penyimpangan yang bervariasi?

Key theories

Jam logis Lamport

Setiap proses menyimpan penghitung yang bertambah pada setiap peristiwa dan dibawa pada pesan; stempel waktu yang dihasilkan menghormati 'terjadi-sebelum', dan ikatan yang dipecahkan oleh pengidentifikasi proses menghasilkan urutan total yang konsisten dengan kausalitas.

Sinkronisasi probabilistik dan pulang-pergi

Metode Cristian memperkirakan jam jarak jauh dengan mengukur waktu pulang-pergi dan mengasumsikan penundaan simetris, memberikan batasan probabilistik pada kesalahan sinkronisasi yang dapat dicapai melalui jaringan.

Protokol Waktu Jaringan (NTP)

NTP mengorganisir server waktu ke dalam hierarki berlapis dan menggunakan penyaringan statistik dari pengukuran offset berulang untuk mendisiplinkan jam di seluruh internet hingga dalam milidetik.

Clinical relevance

Jam logis mengurutkan operasi dalam penyimpanan yang direplikasi dan antrean pesan tanpa mempercayai waktu jam dinding, sementara sinkronisasi fisik mendasari basis data yang diurutkan berdasarkan stempel waktu, penelusuran terdistribusi, dan protokol keamanan yang bergantung pada kesalahan jam yang terbatas.

History

Makalah jam logis Lamport tahun 1978 mengubah konsep waktu dalam sistem terdistribusi menjadi gagasan kausal daripada fisik; secara paralel, Cristian dan lainnya mengembangkan sinkronisasi probabilistik, dan NTP Mills menjadi mekanisme standar untuk menjaga jam internet tetap selaras.

Debates

Waktu logis versus fisik untuk mengurutkan operasi

Jam logis menjamin kebenaran kausal tanpa mempercayai jam perangkat keras, tetapi tidak dapat menghubungkan peristiwa dengan waktu nyata; jam fisik memungkinkan penalaran waktu nyata dengan risiko urutan yang salah ketika penyimpangan melebihi penundaan pesan, memotivasi pendekatan hibrida.

Key figures

• Leslie Lamport
• Flaviu Cristian
• David Mills

Seminal works

• lamport1978
• mills1991
• cristian1989

Frequently asked questions

Jika 'a' memiliki stempel waktu Lamport yang lebih kecil dari 'b', apakah 'a' terjadi sebelum 'b'?

Belum tentu—stempel waktu yang lebih kecil konsisten dengan 'terjadi-sebelum' tetapi tidak menyiratkan hal itu, karena peristiwa bersamaan dapat menerima stempel waktu yang berurutan. Untuk memutuskan kausalitas secara tepat, Anda memerlukan jam vektor, bukan jam logis skalar.