کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949838 | 1364259 | 2017 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Odd gossiping
ترجمه فارسی عنوان
شایعات عجیب و غریب
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
شایعات انتشار اطلاعات، شبکه های ارتباطی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Gossiping is an information dissemination process in which each node of a communication network has a piece of information that must be received by all other nodes. Most previous work on this problem has concentrated on networks for which the number of nodes n is even. We investigate networks for which n is odd. We use a linear cost model of communication in which the cost of communication is proportional to the amount of information transmitted. We study two variants of the problem. In synchronous gossiping, the pairwise communications are organized into rounds and all communications in a round start at the same time. In asynchronous gossiping, a pair of nodes can start communicating while communications between other pairs are in progress. We prove lower bounds on the total time to gossip for both synchronous and asynchronous gossiping. The asynchronous lower bound is achievable for some odd values of n, but we prove that no gossip algorithm for n=2kâ1 nodes, kâ¥3, can achieve the bound. For synchronous gossiping, we present an optimal algorithm for n=2kâ1. We conjecture that our synchronous lower bound is exact for all odd n.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 216, Part 3, 10 January 2017, Pages 550-561
Journal: Discrete Applied Mathematics - Volume 216, Part 3, 10 January 2017, Pages 550-561
نویسندگان
Guillaume Fertin, Joseph G. Peters, Lynette Raabe, Charlie Xu,