Mengapa sistem terdistribusi tidak bisa hanya menggunakan jam fisik yang disinkronkan?

Jam fisik cenderung bergeser (drift) dan tidak dapat disinkronkan dengan sempurna di seluruh jaringan dengan penundaan yang bervariasi, sehingga urutan waktu nyata dari dua peristiwa dapat menjadi ambigu. Jam logis dan vektor justru menangkap urutan kausal yang sebenarnya penting untuk kebenaran.

Apa yang membuat snapshot global 'konsisten'?

Snapshot dikatakan konsisten jika, setiap kali snapshot tersebut mencakup penerimaan pesan, snapshot tersebut juga mencakup pengiriman pesan tersebut. Keadaan seperti itu dapat terjadi selama eksekusi, meskipun tidak ada satu pun momen yang pernah diamati secara global.

Waktu dan Keadaan Global

Waktu dan keadaan global berkaitan dengan bagaimana sistem terdistribusi mengurutkan peristiwa dan memahami kondisi kolektifnya ketika tidak ada jam bersama dan tidak ada pandangan global instan.

Temukan Topik dengan PaperMindSegeraFind papers & topics

Tools & resources

Unduh salindia

Learn & explore

VideoSegera

Definition

Dalam sistem terdistribusi, peristiwa terjadi pada proses terpisah tanpa jam bersama; studi tentang waktu dan keadaan global menyediakan relasi dan algoritma—jam logis dan vektor, snapshot, dan pengiriman terurut—yang memungkinkan sistem mengurutkan peristiwa secara kausal dan menangkap keadaan global yang konsisten.

Scope

Area ini mencakup jam logis dan relasi "terjadi-sebelum" (happened-before), sinkronisasi jam fisik, jam vektor dan deteksi kausalitas serta konkurensi, penentuan snapshot global yang konsisten, dan jaminan pengurutan (FIFO, kausal, total) yang diperlukan untuk multicast yang andal. Bersama-sama, alat-alat ini memungkinkan sistem terdistribusi membuat pernyataan yang bermakna tentang 'kapan' dan 'keadaan apa' meskipun tidak ada jam global.

Sub-topics

Core questions

Bagaimana peristiwa pada proses yang berbeda dapat diurutkan tanpa jam fisik bersama?
Bagaimana suatu proses dapat menentukan apakah dua peristiwa memiliki hubungan kausal atau konkuren?
Bagaimana snapshot global yang konsisten dapat direkam saat komputasi terus berlanjut?
Jaminan pengurutan pengiriman pesan apa yang diperlukan untuk menjaga kausalitas?

Key theories

Terjadi-sebelum (Happened-before) dan jam logis: Relasi "terjadi-sebelum" (happened-before) Lamport mendefinisikan urutan kausal parsial pada peristiwa, dan jam logis (skalar) menetapkan stempel waktu yang konsisten dengannya, menyediakan gagasan urutan tanpa jam yang cukup untuk membangun urutan total untuk banyak protokol.
Jam vektor dan kausalitas: Jam vektor memperluas jam logis sehingga perbandingan dua stempel waktu secara tepat menangkap apakah suatu peristiwa secara kausal mendahului peristiwa lain atau apakah keduanya konkuren, memungkinkan pelacakan kausalitas yang tepat.
Snapshot global yang konsisten: Algoritma snapshot Chandy-Lamport merekam keadaan global yang konsisten—keadaan proses ditambah pesan dalam perjalanan—tanpa menghentikan sistem, dengan menyebarkan penanda di sepanjang saluran.

Clinical relevance

Jam logis dan vektor mendasari konsistensi kausal, deteksi konflik dalam penyimpanan yang direplikasi, dan debugging eksekusi terdistribusi; snapshot yang konsisten mendasari checkpointing terdistribusi, deteksi deadlock dan terminasi, serta pemulihan kesalahan pemrosesan aliran (stream-processing fault recovery).

History

Makalah Lamport tahun 1978 memperkenalkan waktu logis dan relasi "terjadi-sebelum" (happened-before), salah satu hasil yang paling banyak dikutip dalam ilmu komputer; Chandy dan Lamport memformalkan snapshot global yang konsisten pada tahun 1985; dan Fidge serta Mattern secara independen mengembangkan jam vektor pada akhir tahun 1980-an, melengkapi perangkat dasar untuk memahami waktu dan keadaan.

Key figures

Leslie Lamport
K. Mani Chandy
Colin Fidge
Friedemann Mattern

Seminal works

lamport1978
chandy1985
fidge1988

Frequently asked questions

Mengapa sistem terdistribusi tidak bisa hanya menggunakan jam fisik yang disinkronkan?: Jam fisik cenderung bergeser (drift) dan tidak dapat disinkronkan dengan sempurna di seluruh jaringan dengan penundaan yang bervariasi, sehingga urutan waktu nyata dari dua peristiwa dapat menjadi ambigu. Jam logis dan vektor justru menangkap urutan kausal yang sebenarnya penting untuk kebenaran.
Apa yang membuat snapshot global 'konsisten'?: Snapshot dikatakan konsisten jika, setiap kali snapshot tersebut mencakup penerimaan pesan, snapshot tersebut juga mencakup pengiriman pesan tersebut. Keadaan seperti itu dapat terjadi selama eksekusi, meskipun tidak ada satu pun momen yang pernah diamati secara global.