Browsing by Author "Cihan, Onur."

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Convergence rate analysis and optimization of distributed consensus algorithms
    (Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2014., 2014.) Cihan, Onur.; Akar, Mehmet.
    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.
  • Thumbnail Image
    Item
    Distributed synchronization in delayed and topology varying networks
    (Thesis (M.S.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2009., 2009.) Cihan, Onur.; Akar, Mehmet.
    There are numerous network applications where nodes require a common notion of time, and as such distributed synchronization is an important task in topology varying networks. In this thesis, we introduce a well known averaging based distributed synchronization algorithm and investigate its convergence conditions under varying topologies and delay. When data are transmitted through the network, communication delays are un- avoidable and it might degrade system performance. Furthermore, delay can cause a stable system go unstable unless certain conditions are met. In this thesis, the conver- gence of the consensus algorithm for delay varying networks is studied using properties of scrambling matrices. It is shown that delay does not affect the convergence of the algorithm so long as it is bounded. The effect of delay on convergence speed for some well known topologies is also discussed. In order to reduce convergence time, fastest converging system matrices are found for networks with symmetric connections by us- ing Linear Matrix Inequalities. It is also shown that the fastest converging matrices for fixed topologies will not provide the fastest convergence for varying topology networks. Consensus algorithms are investigated for networks not only with non–faulty nodes, but also with the faulty ones (or Byzantine nodes) that try to obstruct syn- chronization by sending wrong clock information to other nodes. It is shown that a network with Byzantine nodes will not be synchronized if the network topology and synchronization algorithm do not meet some conditions. Theoretical results are also illustrated by numerical examples.