Periodic gossiping in back-to-back trees

✍ Scribed by Roger Labahn; André Raspaud

• Book ID: 104294741
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 840 KB
• Volume: 75
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(96)00086-8

✦ Synopsis

The d-ary back-to-back tree of height k, BBT~, consists of two complete d-ary trees of height k the leaves of which are identified. For a proper coloring of the edges of BK$ with c > d + 1 colors, we consider periodic gossiping, i.e. full-duplex all-to-all broadcasting in the l-port model where communication is made on a link of color i at any time (round) = imodc.

We present a coloring for which this process finishes within k periods, where a period is the collection of c consecutive rounds. We prove that this is optimal for c = d + 1.