Pengecualian Bersama Terdistribusi dan Pemilihan Pemimpin

Pengecualian bersama dan pemilihan pemimpin adalah masalah koordinasi klasik: memastikan bahwa paling banyak satu proses mengakses sumber daya kritis, dan memilih satu koordinator terkemuka di antara rekan-rekan.

Definition

Pengecualian bersama terdistribusi menjamin bahwa paling banyak satu proses pada satu waktu memegang sumber daya bersama sambil memastikan akses akhirnya untuk semua pemohon; pemilihan pemimpin secara deterministik memilih tepat satu proses sebagai koordinator, dengan semua proses menyetujui hasilnya.

Scope

Topik ini mencakup algoritma pengecualian bersama berbasis izin (algoritma stempel waktu Lamport, Ricart-Agrawala, pendekatan kuorum Maekawa) dan algoritma berbasis token, beserta kompleksitas pesan dan properti keadilannya; serta algoritma pemilihan pemimpin untuk cincin (Chang-Roberts) dan jaringan umum (algoritma bully), termasuk asumsi mereka tentang pengidentifikasi dan sinkronisitas. Primitif ini berulang di seluruh layanan koordinasi dan sistem tereplikasi.

Core questions

• Bagaimana proses dapat menserialisasi akses ke sumber daya bersama hanya dengan menggunakan pesan?
• Apa saja pertukaran kompleksitas pesan dan keadilan antara skema berbasis izin dan berbasis token?
• Bagaimana seorang pemimpin unik dipilih, dan bagaimana pemilihan dipicu kembali setelah pemimpin gagal?

Key theories

Pengecualian bersama berbasis izin

Algoritma seperti Ricart-Agrawala mengurutkan permintaan berdasarkan stempel waktu logis dan memberikan izin masuk setelah pemohon menerima izin dari semua (atau kuorum) rekan, mencapai keadilan dengan biaya pesan terbatas per entri bagian kritis.

Pengecualian bersama berbasis token

Token unik beredar atau diminta sesuai permintaan, dan hanya pemegangnya yang boleh memasuki bagian kritis, mengurangi lalu lintas pesan tetapi memerlukan mekanisme untuk meregenerasi token yang hilang setelah kegagalan.

Pemilihan pemimpin

Algoritma pemilihan seperti Chang-Roberts untuk cincin dan algoritma bully untuk jaringan umum menggunakan pengidentifikasi proses untuk menyatu pada satu koordinator prioritas tertinggi yang diakui oleh semua proses yang benar.

Clinical relevance

Pemilihan pemimpin dipanggil setiap kali sistem tereplikasi harus memilih primer atau koordinator, dan penguncian terdistribusi menggeneralisasi pengecualian bersama; keduanya diekspos sebagai layanan inti oleh sistem koordinasi yang digunakan di seluruh infrastruktur cloud.

History

Makalah jam logis Lamport tahun 1978 memperkenalkan algoritma pengecualian bersama berbasis stempel waktu; Ricart dan Agrawala mengoptimalkannya pada tahun 1981, Maekawa memperkenalkan kuorum tak lama setelah itu, dan algoritma bully Garcia-Molina tahun 1982 memformalkan pemilihan pemimpin, memberikan bidang ini algoritma koordinasi kanoniknya.

Key figures

• Leslie Lamport
• Glenn Ricart
• Ashok Agrawala
• Hector Garcia-Molina

Seminal works

• ricart1981
• garcia-molina1982
• lynch1996

Frequently asked questions

Bagaimana pengecualian bersama terdistribusi berbeda dari kunci pada satu mesin?

Tidak ada memori bersama atau manajer kunci pusat untuk diandalkan, sehingga proses harus berkoordinasi murni dengan bertukar pesan dan harus secara eksplisit menangani penundaan pesan dan kegagalan, yang dapat dianggap remeh oleh kunci satu mesin.