A Powerful Heuristic for Gossiping

telephone model is presented. The heuristic is fast: for a network
with $n$ nodes and $m$ edges, requiring $R$ rounds for gossiping, the
running time is $\go{R \cdot n \cdot \log n \cdot m}$ for all tested
classes of graphs. This moderate time consumption allows to compute
gossiping schedules for networks with more than 10,000 PUs and
100,000 connections. The heuristic is good: in practice the computed
schedules never exceed the optimum by more than a few rounds. The
heuristic is versatile: it can also be used for broadcasting and
more general information dispersion patterns. It can handle both the
unit-cost and the linear-cost model.

Actually, the heuristic is so good, that for CCC, shuffle-exchange,
butterfly de Bruijn, star and pancake networks the constructed
gossiping schedules are better than the best theoretically derived
ones. For example, for gossiping on a shuffle-exchange network with
$2^{13}$ PUs, the former upper bound was 49 rounds, while our
heuristic finds a schedule requiring 31 rounds. Also for broadcasting
the heuristic improves on many formerly known results.

A second heuristic, works even better for CCC, butterfly, star and
pancake networks. For example, with this heuristic we found that
gossiping on a pancake network with $7!$ PUs can be performed in 15
rounds, 2 fewer than achieved by the best theoretical construction.
This second heuristic is less versatile than the first, but by
refined search techniques it can tackle even larger problems, the
main limitation being the storage capacity. Another advantage is that
the constructed schedules can be represented concisely.