Gossip algorithm with nonuniform clock distribution: optimization over classical and quantum networks

DOI10.1002/OCA.2562zbMATH Open1467.93135arXiv1512.03551OpenAlexW2998653593WikidataQ126461701 ScholiaQ126461701MaRDI QIDQ5000772FDOQ5000772

Authors: Saber Jafarizadeh 

Publication date: 15 July 2021

Published in: Optimal Control Applications \& Methods (Search for Journal in Brave)

Abstract: Distributed gossip algorithm has been studied in literature for practical implementation of the distributed consensus algorithm as a fundamental algorithm for the purpose of in-network collaborative processing. This paper focuses on optimizing the convergence rate of the gossip algorithm for both classical and quantum networks. A novel model of the gossip algorithm with non-uniform clock distribution is proposed which can reach the optimal convergence rate of the continuous-time consensus algorithm. It is described that how the non-uniform clock distribution is achievable by modifying the rate of the Poisson process modeling the clock of the gossip algorithm. The minimization problem for optimizing the asymptotic convergence rate of the proposed gossip algorithm and its corresponding semidefinite programming formulation is addressed analytically. It is shown that the optimal results obtained for uniform clock distribution are suboptimal compared to those of the non-uniform one and for non-uniform distribution the optimal answer is not unique i.e. there is more than one set of probabilities that can achieve the optimal convergence rate. Based on the optimal continuous-time consensus algorithm and the detailed balance property, an effective method of obtaining one of these optimal answers is proposed. Regarding quantum gossip algorithm, by expanding the density matrix in terms of the generalized Gell-Mann matrices, the evolution equation of the quantum gossip algorithm is transformed to the state update equation of the classical gossip algorithm. By defining the quantum gossip operator, the original optimization problem is formulated as a convex optimization problem, which can be addressed by semidefinite programming.

Full work available at URL: https://arxiv.org/abs/1512.03551

Recommendations

• Gossip algorithms in quantum networks
• Distributed average consensus via gossip algorithm with real-valued and quantized data for \(0<q<1\)
• Gossip consensus algorithms via quantized communication
• Optimizing the convergence rate of the quantum consensus: a discrete-time model
• An asynchronous randomized gossip consensus algorithm with nonuniform-selected probability and optimization

zbMATH Keywords

optimal convergence ratequantum networksdistributed gossip algorithm

Mathematics Subject Classification ID

Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Quantum control (81Q93) Networked control (93B70)

Cited In (5)

• Optimal curing resource allocation for epidemic spreading processes
• Optimizing the convergence rate of the quantum consensus: a discrete-time model
• Gossip algorithms in quantum networks
• An asynchronous randomized gossip consensus algorithm with nonuniform-selected probability and optimization
• Convergence rate of Markov chains over switching distance regular networks

This page was built for publication: Gossip algorithm with nonuniform clock distribution: optimization over classical and quantum networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5000772)