NDLI: Location-Aided Fast Distributed Consensus in Wireless Networks

Content Provider	IEEE Xplore Digital Library
Author	Wenjun Li Huaiyu Dai Yanbing Zhang
Copyright Year	1963
Abstract	Existing works on distributed consensus explore linear iterations based on reversible Markov chains, which contribute to the slow convergence of the algorithms. It has been observed that by overcoming the diffusive behavior of reversible chains, certain nonreversible chains lifted from reversible ones mix substantially faster than the original chains. In this paper, the idea of Markov chain lifting is studied to accelerate the convergence of distributed consensus, and two general pseudoalgorithms are presented. These pseudoalgorithms are then instantiated through a class of location-aided distributed averaging (LADA) algorithms for wireless networks, where nodes' coarse location information is used to construct nonreversible chains that facilitate distributed computing and cooperative processing. Our first LADA algorithm is designed for grid networks; for a k × k grid network, it achieves an ε-averaging time of O(k log(ε^-1)). Based on this algorithm, in a wireless network with transmission range r, an ε-averaging time of O(r^-1 log(ε^-1)) can be attained through a centralized algorithm. Subsequently, a distributed LADA algorithm is presented, achieving the same scaling law in averaging time as the centralized scheme in wireless networks for all r satisfying the connectivity requirement; the constructed chain also attains the optimal scaling law in terms of an important mixing metric, the fill time, in its class. Finally, a cluster-based LADA algorithm is proposed, which, requiring no central coordination, provides the additional benefit of reduced message complexity compared with the distributed LADA algorithm.
Sponsorship	IEEE Information Theory Society
Starting Page	6208
Ending Page	6227
Page Count	20
File Size	1094924
File Format	PDF
ISSN	00189448
Volume Number	56
Issue Number	12
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-12-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Wireless networks Distributed computing Markov processes Convergence Algorithm design and analysis Clustering algorithms time complexity Clustering distributed computation distributed consensus message complexity mixing time nonreversible Markov chains
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

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

1 accelerating distributed consensus via lifting markov chains.

Distributed Averaging Via Lifted Markov Chains

Cluster-Based Fast Distributed Consensus

Consensus Propagation

Accelerating Distributed Consensus Via Lifting Markov Chains

The Impact of Mobility on Gossip Algorithms

Markov Approximation for Combinatorial Network Optimization

Location-Aided Fast Distributed Averaging

Order-Optimal Consensus Through Randomized Path Averaging

Location-Aided Fast Distributed Consensus in Wireless Networks

Similar Documents

1 accelerating distributed consensus via lifting markov chains.

Distributed Averaging Via Lifted Markov Chains

Cluster-Based Fast Distributed Consensus

Consensus Propagation

Accelerating Distributed Consensus Via Lifting Markov Chains

The Impact of Mobility on Gossip Algorithms

Markov Approximation for Combinatorial Network Optimization

Location-Aided Fast Distributed Averaging

Order-Optimal Consensus Through Randomized Path Averaging

Location-Aided Fast Distributed Consensus in Wireless Networks