A Classification of Weak Models of Distributed Computing
Tuomo Lempiäinen · Työväentutkimus Vuosikirja · 2014
In this thesis we study the theoretical foundations of distributed computing. Distributed computing is concerned with graphs, where each node is a computing unit and runs the same algorithm. The graph serves both as a communication network and as an input for the algorithm. Each node communicates with adjacent nodes in a synchronous manner and eventually produces its own output. All the outputs together constitute a solution to a problem related to the structure of the graph. The main resource of interest is the amount of information that nodes need to exchange. Hence the running time of an algorithm is defined as the number of communication rounds; any amount of local computation is allowed. We introduce several models of distributed computing that are weaker versions of the well-established port-numbering model. In the port-numbering model, a node of degree d has d input ports and d output ports, both numbered with 1, 2, ..., d such that the port numbers are consistent. We denote by VVc the class of all graph problems that can be solved in this model. We define the following subclasses of VVc, corresponding to the weaker models: VV: Input and output port numbers are not necessarily consistent. MV: Input ports are not numbered; nodes receive a multiset of messages. SV: Input ports are not numbered; nodes receive a set of messages. VB: Output ports are not numbered; nodes broadcast the same message to all neighbours. MB: Combination of MV and VB. SB: Combination of SV and VB. This thesis presents a complete classification of the computational power of the models. We prove that the corresponding complexity classes form the following linear order: SB ⊈ MB = VB ⊈ SV = MV = VV ⊈ VVc. To prove SV = MV, we show that any algorithm receiving a multiset of messages can be simulated by an algorithm that receives only a set of messages. The simulation causes an additive overhead of 2∆ - 2 communication rounds, where ∆ is an upper bound for the maximum degree of the graph. As a new result, we prove that the simulation is optimal: it is not possible to achieve a simulation overhead smaller than 2∆ - 2. Furthermore, we construct a graph problem that can be solved in one round of communication by an algorithm receiving a multiset of messages, but requires at least ∆ rounds when solved by an algorithm receiving only a set of messages.