Süper stabilizasyon - Superstabilization

Süper stabilizasyon bir kavramdır hata toleransı içinde dağıtılmış hesaplama. Süper stabilize etme dağıtılmış algoritmalar özelliklerini birleştirmek kendi kendini dengeleyen algoritmalar ve dinamik algoritmalar. Süper stabilize edici bir algoritma - tıpkı diğer herhangi bir kendi kendini stabilize eden algoritma gibi - keyfi bir durumda başlatılabilir ve Sonuçta meşru bir duruma yaklaşmak. Ek olarak, süper stabilize edici bir algoritma kurtarılacaktır. hızla ağ topolojisindeki tek bir değişiklikten (ağa bir kenar veya düğüm ekleme veya çıkarma).

Kendi kendini stabilize eden herhangi bir algoritma, ağ topolojisindeki bir değişiklikten kurtarır - bir topoloji değişikliğinden sonraki sistem konfigürasyonu, diğer herhangi bir rastgele başlatma konfigürasyonu gibi ele alınabilir. Bununla birlikte, kendi kendini dengeleyen bir algoritmada, ağ topolojisindeki tek bir değişiklikten sonra yakınsama, rastgele bir başlangıç ​​durumundan gelen yakınsama kadar yavaş olabilir. Süper stabilize edici algoritmalar çalışmasında, ağ topolojisindeki tek bir değişiklikten kurtulmak için gereken süreye özel dikkat gösterilir.

Tanımlar

stabilizasyon süresi Bir süper stabilize edici algoritmanın, kendi kendini stabilize eden algoritma durumunda olduğu gibi tanımlanır: keyfi bir konfigürasyondan meşru bir duruma yakınsamanın ne kadar sürdüğü. Hesaplama modeline bağlı olarak, zaman ölçülür, örneğin senkron iletişim turlarında veya asenkron döngülerde.

süper stabilizasyon süresi tek bir topoloji değişikliğinden kurtarma zamanıdır. Sistemin başlangıçta meşru bir konfigürasyonda olduğu varsayılmaktadır. Ardından ağ topolojisi değiştirilir; süper stabilizasyon süresi, sistemin yeniden meşru bir konfigürasyona ulaşması için geçen maksimum süredir. Benzer şekilde, ayarlama ölçüsü bu tür değişikliklerden sonra durumlarını değiştirmek zorunda olan maksimum düğüm sayısıdır.

Bir topoloji değişikliğinden sonra meydana gelen "neredeyse meşru konfigürasyonlar" kullanılarak resmi olarak modellenebilir. geçit yüklemleri: bir geçiş koşulu, ağ topolojisindeki tek bir değişiklikten sonra ve ayrıca meşru bir yapılandırmaya yakınsama sırasında tutan bir yüklemdir.

Referanslar

• Dolev, Shlomi; Herman, Ted (1997), "Dinamik dağıtılmış sistemler için süper stabilize edici protokoller", Chicago Teorik Bilgisayar Bilimleri Dergisi4. madde.
• Dolev, Shlomi (2000), Kendini Dengeleme, MIT Basın, ISBN  0-262-04178-2, Bölüm 7.1.