Arşiv ve Dokümantasyon Merkezi
Dijital Arşivi

Convergence rate analysis and optimization of distributed consensus algorithms

Basit öğe kaydını göster

dc.contributor Ph.D. Program in Electrical and Electronic Engineering.
dc.contributor.advisor Akar, Mehmet.
dc.contributor.author Cihan, Onur.
dc.date.accessioned 2023-03-16T10:25:08Z
dc.date.available 2023-03-16T10:25:08Z
dc.date.issued 2014.
dc.identifier.other EE 2014 C54 PhD
dc.identifier.uri http://digitalarchive.boun.edu.tr/handle/123456789/13114
dc.description.abstract 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.
dc.format.extent 30 cm.
dc.publisher Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2014.
dc.subject.lcsh Algorithms.
dc.subject.lcsh Mathematical optimization.
dc.subject.lcsh Markov processes.
dc.title Convergence rate analysis and optimization of distributed consensus algorithms
dc.format.pages xiv, 78 leaves ;


Bu öğenin dosyaları

Bu öğe aşağıdaki koleksiyon(lar)da görünmektedir.

Basit öğe kaydını göster

Dijital Arşivde Ara


Göz at

Hesabım