کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4951617 1441476 2017 24 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A local average broadcast gossip algorithm for fast global consensus over graphs
ترجمه فارسی عنوان
یک الگوریتم شایعات به طور متوسط ​​پخش محلی برای توافق سریع جهانی بر روی نمودارها
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Motivated by applications to wireless sensor, peer-to-peer, and social networks, the canonical average consensus problem is considered in random and regular graphs in this paper. A local average information exchange (LAIE) algorithm is developed to compute the global consensus of the initial measurements of the nodes at every node in the network. In the proposed algorithm, each node interacts with all of its neighboring nodes in each round of the diffusion process to compute and exchange the local average value, such that all nodes can asymptotically reach a global consensus in a distributed manner very quickly. This is in contrast to the conventional random gossip scheme, where each node only interacts with one of its neighboring nodes, leading to very long convergence time. Results show that in a random graph with n nodes, the convergence time of the LAIE algorithm is bounded below by Ω(n−1)lognΔ,1 where the parameter Δ denotes the largest degree of the graphs. When a network has n nodes represented by d-regular topology graphs (d>2), where each node has the same number of neighbors d, the convergence time of the LAIE algorithm is bounded below by Θn(d+1)logn(2+d+2d−1)(d−2d−1). This shows that the proposed algorithms can achieve quicker convergence to the global consensus than other schemes based on the classic random gossip algorithm. Finally, we assess and compare the communication cost of the local average algorithm to achieve consensus through numerical results.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 109, November 2017, Pages 301-309
نویسندگان
, , ,