{'fraction_non_alphanumeric': 0.01691542288557214, 'fraction_numerical': 0.0, 'mean_word_length': 4.828985507246377, '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}}
The price of locality: exploring the complexity of distributed coordination primitives

In a distributed computation, many autonomous processors intend to jointly come up with a solution for a given problem. It is usually assumed that the processors are located at different sites and are connected to each other by a network. Coordination between different processors (also called network nodes) is done by exchanging messages. If the input for a given problem is distributed among the nodes of the network, nodes need to communicate in order to learn about each other’s input. In k units of time, it is only possible to send information to nodes at distance at most k in the network. If the diameter of a given network is large, no node can learn about the whole network. In a few time units, a node can only gather data from nearby nodes. Thus, all nodes have to base their computations on partial information. Nevertheless, all network nodes together have to reach a common solution for the problem at hand. Achieving a global goal based on local information is therefore one of the most fundamental problems in the area of distributed computing. This thesis considers the complexity of different important distributed coordination tasks. In particular, three major problems are discussed. First, we establish nearly tight upper and lower bounds on the possible trade-offs between running time and quality of the solution for a class of problems called covering and packing problems. Prominent network-related members of this problem class are for example minimum dominating set and maximum matching. Second, we consider protocols for coloring the nodes of the network. We analyze the potential of the simplest coloring algorithms where each node decides on a color based on the colors or identifiers of its direct neighbors only. Third, we study the distributed complexity of problems on a special kind of network topologies occurring in the context of wireless networks such as ad hoc or sensor networks.