Dağıtık Karşılıklı Dışlama ve Lider Seçimi
Karşılıklı dışlama ve lider seçimi, klasik koordinasyon problemleridir: en fazla bir sürecin kritik bir kaynağa erişmesini sağlamak ve eşler arasında tek bir seçkin koordinatör seçmek.
Tanım
Dağıtık karşılıklı dışlama, tüm talep edenler için nihai erişimi sağlarken, aynı anda en fazla bir sürecin paylaşılan bir kaynağı tutmasını garanti etmektedir; lider seçimi ise tam olarak bir süreci koordinatör olarak deterministik bir şekilde seçmekte ve tüm süreçler sonuç üzerinde anlaşmaktadır.
Kapsam
Bu konu, izin tabanlı karşılıklı dışlama algoritmalarını (Lamport'un zaman damgası algoritması, Ricart-Agrawala, Maekawa'nın kota yaklaşımı) ve belirteç tabanlı algoritmaları, mesaj karmaşıklıkları ve adillik özellikleriyle birlikte ele almaktadır; ayrıca halkalar (Chang-Roberts) ve genel ağlar (zorba algoritması) için lider seçimi algoritmalarını, tanımlayıcılar ve senkronizasyon hakkındaki varsayımları da dahil olmak üzere kapsamaktadır. Bu temel öğeler, koordinasyon hizmetleri ve çoğaltılmış sistemler boyunca tekrar tekrar karşımıza çıkmaktadır.
Temel sorular
- Süreçler, yalnızca mesajları kullanarak paylaşılan bir kaynağa erişimi nasıl sıralayabilir?
- İzin tabanlı ve belirteç tabanlı şemalar arasındaki mesaj karmaşıklığı ve adillik dengeleri nelerdir?
- Benzersiz bir lider nasıl seçilir ve lider başarısız olduktan sonra seçim nasıl yeniden tetiklenir?
Temel kuramlar
- İzin tabanlı karşılıklı dışlama
- Ricart-Agrawala gibi algoritmalar, istekleri mantıksal zaman damgalarına göre sıralamakta ve bir talep edenin tüm (veya bir kota kadar) eşlerden izin aldıktan sonra girişi sağlamaktadır; bu, kritik bölüm giriş başına sınırlı mesaj maliyeti ile adillik sağlamaktadır.
- Belirteç tabanlı karşılıklı dışlama
- Benzersiz bir belirteç dolaşmakta veya talep üzerine istenmekte ve yalnızca belirteci elinde bulunduran kritik bölüme girebilmektedir; bu, mesaj trafiğini azaltmakla birlikte, arızalardan sonra kaybolan bir belirteci yeniden oluşturmak için mekanizmalar gerektirmektedir.
- Lider seçimi
- Halkalar için Chang-Roberts ve genel ağlar için zorba algoritması gibi seçim algoritmaları, tüm doğru süreçlerin tanıdığı tek bir en yüksek öncelikli koordinatör üzerinde birleşmek için süreç tanımlayıcılarını kullanmaktadır.
Klinik önem
Lider seçimi, çoğaltılmış bir sistemin birincil veya koordinatör seçmesi gerektiğinde devreye girmektedir ve dağıtık kilitleme, karşılıklı dışlamayı genelleştirmektedir; her ikisi de bulut altyapısı genelinde kullanılan koordinasyon sistemleri tarafından temel hizmetler olarak sunulmaktadır.
Tarihçe
Lamport'un 1978 tarihli mantıksal saat makalesi, zaman damgası tabanlı bir karşılıklı dışlama algoritması sunmuştur; Ricart ve Agrawala 1981'de bunu optimize etmiş, Maekawa kısa bir süre sonra kotaları tanıtmış ve Garcia-Molina'nın 1982 tarihli zorba algoritması lider seçimini resmileştirerek alana kanonik koordinasyon algoritmalarını kazandırmıştır.
Öne çıkan isimler
- Leslie Lamport
- Glenn Ricart
- Ashok Agrawala
- Hector Garcia-Molina
İlgili konular
Temel eserler
- ricart1981
- garcia-molina1982
- lynch1996
Sıkça sorulan sorular
- Dağıtık karşılıklı dışlama, tek bir makinedeki kilitten nasıl farklıdır?
- Dayanılacak paylaşılan bir bellek veya merkezi bir kilit yöneticisi bulunmamaktadır, bu nedenle süreçler yalnızca mesaj alışverişi yoluyla koordine olmak zorundadır ve tek bir makine kilidinin varsayabileceği mesaj gecikmesi ve arızaları açıkça ele almalıdır.