{'fraction_non_alphanumeric': 0.033795493934142114, 'fraction_numerical': 0.006065857885615251, 'mean_word_length': 4.44811320754717, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, '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}}
Time-communication trade-offs for minimum spanning tree construction

This paper concerns the problem of constructing a minimum spanning tree (MST) in a synchronous distributed network with n nodes, where each node knows only the identities of itself and its neighbors. We assume the CONGEST model where messages are of size O(log n) bits. Spanning tree construction was long believed to require an amount of communication linear in the number of edges. In 2015, King, Kutten and Thorup presented a Monte Carlo algorithm which broke this communication bound. In particular it showed that an MST could be constructed with time and message complexity O(n log2 n/log log n), independent of the number of edges. Here we give trade-offs between time and communication. Our Monte Carlo algorithm runs in O(n/ϵ) time and O(n1+ϵ/ϵ log log n) messages for any 1 > ϵ ≥ log log n log n. For the spanning tree problem, we show a time bound of O(n) and a communication bound of O(n log n log log n) messages. We also provide the first algorithm that constructs an MST in time proportional to the diameter of the MST up to a logarithmic factor with o(m) communication.