{'fraction_non_alphanumeric': 0.03744292237442922, 'fraction_numerical': 0.0365296803652968, 'mean_word_length': 4.269230769230769, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Lower bounds on systolic gossip

Gossiping is an information dissemination process in which each processor has a distinct item of information and has to collect all the items possessed by the other processors. We derive lower bounds on the gossiping time of systolic protocols, i.e. constituted by a periodic repetition of simple communication steps. In particular if we denote by n the number of processors in the network, then for directed networks and for undirected networks in the half-duplex mode any s-systolic gossip protocol takes at least g(s) log/sub 2/ n time steps, where g(4)=1.8133, g(6)=1.5310 and g(8)=1.4721. For the case s=4 this result is improved to 2.0218 log/sub 2/ n for directed butterflies of degree 2 and we show that the 2.0218 log/sub 2/ n and 1.8133 log/sub 2/ n lower bounds hold also respectively for undirected Butterfly and de Bruijn networks of degree 2 in the full-duplex case. Our results are obtained by means of new technique relying on two novel concepts in the field: the notion of delay digraph of a systolic protocol and the use of matrix norm methods.