NDLI: Analysis and optimization of randomized gossip algorithms

Content Provider	IEEE Xplore Digital Library
Author	Boyd, S. Ghosh, A. Prabhakar, B. Shah, D.
Copyright Year	2004
Description	Author affiliation: Inf. Syst. Lab., Stanford Univ., CA, USA (Boyd, S.; Ghosh, A.; Prabhakar, B.; Shah, D.)
Abstract	We study the distributed averaging problem on an arbitrary network with a gossip constraint, which means that no node communicates with more than one neighbour in every time slot. We consider algorithms which are linear iterations, where each iteration is described by a random matrix picked i.i.d. from some distribution. We derive conditions that this distribution must satisfy so that the sequence of iterations converges to the vector of averages in different senses. We then analyze a simple asynchronous randomized gossip algorithm for averaging, and show that the problem of optimizing the parameters of this algorithm for fastest convergence is a semi-definite program. Finally we study the relation between Markov chains and the averaging problem, and relate the averaging time of the algorithm to the mixing time of a related Markov chain on the graph.
Starting Page	5310
Ending Page	5315
File Size	175288
Page Count	6
File Format	PDF
ISBN	0780386825
ISSN	01912216
DOI	10.1109/CDC.2004.1429652
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2004-12-14
Publisher Place	Bahamas
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Algorithm design and analysis Convergence Vectors Information systems Laboratories Protocols Context Distributed computing Circuits and systems Contracts
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Decentralized K-Means Using Randomized Gossip Protocols for Clustering Large Datasets

Gossip algorithms for clustering problems

Randomized gossip algorithms for solving Laplacian systems

On distributed optimization using generalized gossip

Asynchronous gossip algorithms for stochastic optimization

Almost-Optimal Gossip-Based Aggregate Computation

Fast Distributed Algorithms for Computing Separable Functions

Gossip and consensus in mobile networks

Metarouting and Network Optimization

Analysis and optimization of randomized gossip algorithms

Similar Documents

Decentralized K-Means Using Randomized Gossip Protocols for Clustering Large Datasets

Gossip algorithms for clustering problems

Randomized gossip algorithms for solving Laplacian systems

On distributed optimization using generalized gossip

Asynchronous gossip algorithms for stochastic optimization

Almost-Optimal Gossip-Based Aggregate Computation

Fast Distributed Algorithms for Computing Separable Functions

Gossip and consensus in mobile networks

Metarouting and Network Optimization

Analysis and optimization of randomized gossip algorithms