Non asymptotic bounds in asynchronous sum-weight gossip protocols
This paper focuses on non-asymptotic diffusion time in asynchronous gossip protocols. Asynchronous gossip protocols are designed to perform distributed computation in a network of nodes by randomly exchanging messages on the associated graph. To achieve consensus among nodes, a minimal number of messages has to be exchanged. We provides a probabilistic bound to such number for the general case. We provide a explicit formula for fully connected graphs depending only on the number of nodes and an approximation for any graph depending on the spectrum of the graph.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Everyone Knows that Everyone Knows: Gossip Protocols for Super Experts
A gossip protocol is a procedure for sharing secrets in a network. The basic action in a gossip protocol is a pairwise message exchange (telephone call) wherein the calling agents exchange all the secrets they know. An a…
AllDIGEST: Fast and Communication Efficient Decentralized Learning with Local Updates
Two widely considered decentralized learning algorithms are Gossip and random walk-based learning. Gossip algorithms (both synchronous and asynchronous versions) suffer from high communication cost, while random-walk bas…
Epistemic Protocols for Distributed Gossiping
Gossip protocols aim at arriving, by means of point-to-point or group communications, at a situation in which all the agents know each other's secrets. We consider distributed gossip protocols which are expressed by mean…
GossipGraD: Scalable Deep Learning using Gossip Communication based Asynchronous Gradient Descent
In this paper, we present GossipGraD - a gossip communication protocol based Stochastic Gradient Descent (SGD) algorithm for scaling Deep Learning (DL) algorithms on large-scale systems. The salient features of GossipGra…
CPUDeep LearningGPUFast and Efficient Gossip Algorithms for Robust and Non-smooth Decentralized Learning
Decentralized learning on resource-constrained edge devices demands algorithms that are communication-efficient, robust to data corruption, and lightweight in memory. State-of-the-art gossip-based methods address communi…