Convergence rate analysis and optimization of distributed consensus algorithms
Dağıtık onaylaşım algoritmalarının yakınsama hızı analizi ve en iyilemesi
- Tez No: 355756
- Danışmanlar: DOÇ. DR. MEHMET AKAR
- Tez Türü: Doktora
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2014
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
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.
Özet (Çeviri)
The problem of achieving a common value in a distributed information sharing context, referred to as distributed consensus or agreement, is an important topic that has drawn significant research attention of late. Consensus algorithms find applications in many areas including network clock synchronization, sensor fusion and load balancing where achieving consensus as fast as possible is important. In this dissertation, we study the analysis and optimization of convergence rate of averaging based distributed consensus algorithms evolving on graphs. By relating the convergence speed of the algorithm to the mixing rate of a Markov chain, we propose two semi-definite programming (SDP) methods of assigning transition probabilities to a Markov chain in order to optimize its mixing rate. In the first SDP formulation, there is a single transition probability parameter to be optimized (the holding probability of vertices) which leads to easier and faster computation as opposed to the more general reversible Markov chain formulation corresponding to a stationary distribution that is proportional to the degree of vertices. By deriving exact analytical results, it is shown that both the single parameter and the degree proportional reversible fastest mixing Markov chain formulations yield better results than the symmetric SDP formulation for a path and some well-known edge-transitive and orbit graphs. The convergence rate of the averaging based distributed consensus algorithm is also analyzed for networks where delay exists in data receptions, which is unavoidable in practice. After introducing the delayed version of the consensus algorithm, it is analytically shown that bounded non-uniform delay does not adversely affect its convergence rate for directed acyclic graphs.
Benzer Tezler
- Distributed caching and learning over wireless channels
Kablosuz kanallar üzerinde dağıtık önbelleğe alma ve makine öğrenmesi
BÜŞRA TEGİN
Yüksek Lisans
İngilizce
2020
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. TOLGA METE DUMAN
- Deep learning meets reconfigurable ıntelligentsurfaces: Novel system designs and solutionstoward 6G and beyond
Derin öğrenme, yeniden yapilandirilabilir akilli yüzeylerle buluşuyor: 6G ve ötesine doğru yeni sistem tasarimlari ve çözümleri
YARKIN GEVEZ
Doktora
İngilizce
2025
Elektrik ve Elektronik MühendisliğiKoç ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ERTUĞRUL BAŞAR
- Visible light positioning systems: Fundamental limits, algorithms and resource allocation approaches
Görünür ışık konumlandırma sistemleri: Temel sınırlar, algoritmalar ve kaynak tahsisi yaklaşımları
MUSA FURKAN KESKİN
Doktora
İngilizce
2018
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. SİNAN GEZİCİ
- Hücresel yapay sinir ağları için iki öğrenme algoritması ve görüntü işleme uygulamaları
Two learning algorithms for cellular neural networks and their image processing applications
SİNAN KARAMAHMUT
Yüksek Lisans
Türkçe
1994
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. CÜNEYT GÜZELİŞ
- Konvansiyonel ve mikro şebeke içeren güç sistemlerinde dinamik ekonomik yük ve emisyon dağıtımının sezgisel yöntemlerle analizi
Dynamic economic emission dispatch in power systems with and without microgrids by using heuristic algorithms
ESRA AYDIN
Yüksek Lisans
Türkçe
2022
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. BELGİN TÜRKAY