کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10334017 | 690128 | 2005 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Faster gossiping on butterfly networks
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Faster gossiping on butterfly networks Faster gossiping on butterfly networks](/preview/png/10334017.png)
چکیده انگلیسی
Gossiping has been considered intensively for butterflies and “simple” butterflies (which have no wrap-around connections). In the “telephone” communication model, for a butterfly of order k, the best previous gossiping algorithms require 212k and 3k communication rounds, respectively. By new asymptotic methods we break through these bounds. We show that gossiping on a class of “column-based” networks, which also contains the cube-connected cycles, can be reduced to the simpler problem of “row-gossiping”. Row-gossiping in turn is reduced to “coherent row-broadcasting”. This latter problem is sufficiently simple to be solved by a sophisticated computer program for butterflies with up to 15Ã215 nodes. Out of the produced solutions a pattern is distilled, which can be used to perform gossiping on butterflies and simple butterflies of order k in 214k+o(k) and 212k+o(k) rounds, respectively, for any k, considerably reducing the gap with the lower bounds. The new upper bounds also hold for gossiping in the weaker “telegraph” model.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 331, Issue 1, 15 February 2005, Pages 53-72
Journal: Theoretical Computer Science - Volume 331, Issue 1, 15 February 2005, Pages 53-72
نویسندگان
Jop F. Sibeyn,