Pengurutan Pesan dan Multicast

Komunikasi grup mengirimkan pesan ke sekumpulan proses dengan keandalan dan jaminan pengurutan yang ditentukan, mulai dari FIFO hingga kausal hingga urutan total.

Definition

Multicast mengirimkan satu pesan ke setiap anggota grup proses; jaminan pengurutan membatasi urutan pengiriman relatif pesan, dengan FIFO mempertahankan urutan per pengirim, kausal mempertahankan urutan 'terjadi sebelum' (happened-before), dan urutan total mengirimkan semua pesan dalam urutan yang sama pada setiap anggota.

Scope

Topik ini mencakup multicast yang andal dan hierarki urutan pengiriman—FIFO, kausal, dan total (atomik)—implementasinya menggunakan nomor urut, jam logis, dan skema sequencer atau token, serta model sinkronisasi virtual yang mengintegrasikan multicast terurut dengan perubahan keanggotaan grup yang konsisten. Siaran urutan total (atomik) ditunjukkan setara dalam kekuatan dengan konsensus.

Core questions

• Keandalan dan jaminan pengurutan apa yang dibutuhkan aplikasi dari komunikasi grup?
• Bagaimana urutan pengiriman kausal dan total diimplementasikan secara efisien?
• Mengapa siaran urutan total setara dengan konsensus?

Key theories

Hierarki pengurutan

Urutan pengiriman membentuk hierarki—FIFO lebih lemah dari kausal, yang lebih lemah dari urutan total—masing-masing diberlakukan oleh metadata tambahan seperti nomor urut per pengirim, stempel waktu vektor, atau urutan yang disepakati secara global.

Sinkronisasi virtual

Sinkronisasi virtual menyajikan perubahan keanggotaan grup dan pesan multicast dalam urutan yang konsisten kepada semua anggota, sehingga proses melihat urutan peristiwa dan perubahan tampilan yang sama, menyederhanakan konstruksi layanan tereplikasi.

Siaran atomik sama dengan konsensus

Siaran urutan total (atomik) dan konsensus dapat direduksi satu sama lain, sehingga setiap solusi untuk satu menghasilkan solusi untuk yang lain dan keduanya memiliki batas solvabilitas yang sama di bawah asinkroni dan kegagalan.

Clinical relevance

Multicast yang terurut dan andal adalah substrat dari replikasi mesin keadaan, sistem publish-subscribe, dan basis data tereplikasi, di mana setiap replika harus menerapkan pembaruan yang sama dalam urutan yang sama untuk tetap konsisten.

History

Birman dan Joseph memperkenalkan sinkronisasi virtual dan multicast terurut pada tahun 1980-an melalui sistem ISIS; hubungan antara siaran atomik dan konsensus diklarifikasi pada tahun 1990-an, dan survei Defago, Schiper, dan Urban tahun 2004 mensistematisasi banyak algoritma urutan total.

Key figures

• Kenneth Birman
• Thomas Joseph
• Andre Schiper
• Leslie Lamport

Seminal works

• birman1987
• defago2004
• lamport1978

Frequently asked questions

Apa perbedaan antara pengurutan kausal dan total?

Pengurutan kausal hanya membatasi pesan yang memiliki hubungan kausal, membiarkan pesan bersamaan bebas untuk dikirimkan dalam urutan yang berbeda pada proses yang berbeda. Pengurutan total mengharuskan setiap proses untuk mengirimkan semua pesan dalam urutan yang identik, yang secara ketat lebih kuat dan sesulit konsensus.