Dağıtılmış algoritma - Distributed algorithm

Bir dağıtılmış algoritma bir bir algoritma üzerinde çalışmak üzere tasarlanmış bilgisayar donanım birbirine inşa işlemci . Dağıtılmış algoritmalar, telekomünikasyon , bilimsel hesaplama , dağıtılmış bilgi işleme ve gerçek zamanlı süreç kontrolü gibi dağıtılmış hesaplamanın farklı uygulama alanlarında kullanılmaktadır . Dağıtılmış algoritmalar tarafından çözülen standart problemler arasında lider seçimi , fikir birliği , dağıtılmış arama , yayılan ağaç oluşturma, karşılıklı dışlama ve kaynak tahsisi yer alır .

Dağıtılmış algoritmalar , tipik olarak eşzamanlı olarak yürütülen , algoritmanın ayrı bölümlerinin bağımsız işlemciler üzerinde eşzamanlı olarak çalıştırıldığı ve algoritmanın diğer bölümlerinin ne yaptığı hakkında sınırlı bilgiye sahip olduğu bir paralel algoritma alt türüdür . Dağıtılmış algoritmaları geliştirme ve uygulamadaki en büyük zorluklardan biri, işlemci arızaları ve güvenilmez iletişim bağlantıları karşısında algoritmanın bağımsız bölümlerinin davranışını başarılı bir şekilde koordine etmektir. Belirli bir problemi çözmek için uygun bir dağıtılmış algoritmanın seçimi, hem problemin özelliklerine hem de işlemcinin veya bağlantı hatalarının türü ve olasılığı, süreçler arası iletişimin türü gibi algoritmanın üzerinde çalışacağı sistemin özelliklerine bağlıdır. gerçekleştirilebilir ve ayrı işlemler arasındaki zamanlama senkronizasyonu düzeyi.

Standart problemler

Atomik taahhüt

Atomik taahhüt, bir dizi farklı değişikliğin tek bir işlem olarak uygulandığı bir işlemdir. Atomik taahhüt başarılı olursa, tüm değişikliklerin uygulanmış olduğu anlamına gelir. Atomik kesinleştirme tamamlanmadan önce bir hata olursa, "taahhüt" iptal edilir ve hiçbir değişiklik uygulanmaz.

Atomik kesinleştirme protokolünü çözmeye yönelik algoritmalar, iki aşamalı kesinleştirme protokolünü ve üç aşamalı kesinleştirme protokolünü içerir .

Uzlaşma

Konsensüs algoritmaları, ortak bir karar üzerinde anlaşmaya varan bir takım süreçlerin problemini çözmeye çalışır.

Daha doğrusu, bir Konsensüs protokolü aşağıdaki dört resmi özelliği karşılamalıdır.

• Sonlandırma : Her doğru işlem bir değere karar verir.
• Geçerlilik : Tüm süreçler aynı değeri öneriyorsa, her doğru süreç karar verir .${\görüntüleme stili v}$${\görüntüleme stili v}$
• Bütünlük : Her doğru süreç en fazla bir değere karar verir ve eğer bir değere karar verirse , o zaman bir süreç tarafından önerilmiş olmalıdır.${\görüntüleme stili v}$${\görüntüleme stili v}$
• Anlaşma : Eğer doğru bir süreç karar verirse , o zaman her doğru süreç karar verir .${\görüntüleme stili v}$${\görüntüleme stili v}$

Konsensüs çözmek için yaygın algoritmalar, Paxos algoritması ve Raft algoritmasıdır .

Dağıtılmış arama

lider seçimi

Lider seçimi, birkaç bilgisayar (düğüm) arasında dağıtılan bazı görevlerin düzenleyicisi olarak tek bir süreci belirleme sürecidir. Görev başlamadan önce, tüm ağ düğümleri, görevin "lideri" veya koordinatörü olarak hangi düğümün hizmet vereceğinden habersizdir. Ancak bir lider seçim algoritması çalıştırıldıktan sonra, ağdaki her bir düğüm belirli, benzersiz bir düğümü görev lideri olarak tanır.

Karşılıklı dışlama

Engellenmeyen veri yapıları

Güvenilir Yayın

Güvenilir yayın, dağıtılmış sistemlerde bir iletişim ilkesidir. Güvenilir bir yayın aşağıdaki özelliklerle tanımlanır:

• Geçerlilik - eğer doğru bir süreç bir mesaj gönderirse, o zaman bazı doğru süreçler sonunda o mesajı iletecektir.
• Anlaşma - doğru bir süreç bir mesaj veriyorsa, tüm doğru süreçler sonunda bu mesajı iletir.
• Bütünlük - her doğru işlem, aynı mesajı en fazla bir kez ve yalnızca bu mesaj bir işlem tarafından gönderildiyse iletir.

Güvenilir bir yayın sıralı, nedensel veya toplam sıralamaya sahip olabilir.

çoğaltma

Kaynak tahsisi

Yayılan ağaç üretimi

Simetri kırma, örneğin köşe renklendirme

Referanslar

daha fazla okuma

• Christian Cachin; Rachid Guerraoui; Luís Rodrigues (2011), Güvenilir ve Güvenli Dağıtılmış Programlamaya Giriş (2. baskı), Springer, ISBN 978-3-642-15259-7
• C. Rodríguez, M. Villagra ve B. Barán, Boolean Satisfiability için Asenkron ekip algoritmaları , Bionetics2007, s. 66–69, 2007.

Dış bağlantılar

• İlgili Ortam Dağıtık algoritmalar Wikimedia Commons
• MIT Open Courseware - Dağıtılmış Algoritmalar