Dağıtık onaylaşım algoritmalarının yakınsama hızı analizi ve en iyilemesi

Dağıtık onaylaşım ya da anlaşma olarak anılan, dağıtık bilgi bağlamında ortak bir değere ulaşma problemi, son zamanlarda kayda değer araştırma ilgisi çekmiş önemli bir konudur. Onaylaşım algoritmaları, onaylaşıma mümkün olabildiğince en hızlı şekilde ulaşılmasının önemli olduğu, ağlardaki saat eş zamanlaması, algılayıcı tümleştirmesi, yük dengelemesi gibi birçok uygulamada kullanılmaktadır. Bu tezde, çizgeler üzerinde tanımlanan ortalama tabanlı dağıtık onaylaşım algoritmalarının yakınsama hızı analizi ve en iyilemesi konusunda çalışılmıştır. Algoritmanın yakınsama hızı Markov zincirlerinin karışım hızı ile ilişkilendirilerek, bir Markov zincirine geçiş olasılıklarını atayarak karışım hızını en iyilemeyi amaçlayan iki Yarı-Tanımlı Programlama (YTP) yöntemi önerilmiştir. İlk YTP formülasyonunda, en iyilenen tek bir geçiş olasılığı parametresi (köşelerde kalma olasılığı) vardır ve bu, köşe dereceleriyle orantılı bir kalıcı dağılıma karşılık gelen daha genel tersinir Markov zinciri formülasyonuna nazaran daha kolay ve hızlı hesaplama sağlar. Kesin çözümler elde edilerek, hem tek parametreli hem de dereceyle oransal tersinir en hızlı karışan Markov zincirlerinin bazı tanınmış kenar geçişli ve yörünge çizgeleri için bakışımlı YTP formülasyonundan daha iyi sonuçlar sağladığı gösterilmiştir. Ortalama tabanlı dağıtık onaylaşım algoritmalarının yakınsama hızı, pratikte kaçınılmaz olan veri alışlarında gecikmenin olduğu ağlar için de analiz edilmiştir. Onaylaşım algoritmasının gecikmeli sürümünün tanıtılmasından sonra, sınırlandırılmış bir örnek olmayan gecikmenin yönlendirilmiş çevrimsiz çizgeler için yakınsama hızını olumsuz etkilemediği analitik olarak gösterilmiştir.