This work presents a classification of weak models of distributed computing. We focus on deterministic distributed algorithms, and study models of computing that are weaker versions of the widely-studied port-numbering model. In the port-numbering model, a node of degree @math d receives messages through @math d input ports and sends messages through @math d output ports, both numbered with @math 1 , 2 , ? , d . In this work, @math VV c is the class of all graph problems that can be solved in the standard port-numbering model. We study the following subclasses of @math VV c : Now we have many trivial containment relations, such as @math SB ⊆ MB ⊆ VB ⊆ VV ⊆ VV c , but it is not obvious if, for example, either of @math VB ⊆ SV or @math SV ⊆ VB should hold. Nevertheless, it turns out that we can identify a linear order on these classes. We prove that @math SB ? MB = VB ? SV = MV = VV ? VV c . The same holds for the constant-time versions of these classes. We also show that the constant-time variants of these classes can be characterised by a corresponding modal logic. Hence the linear order identified in this work has direct implications in the study of the expressibility of modal logic. Conversely, one can use tools from modal logic to study these classes.
We are by no means the first to investigate the weak models. Computation in models that are strictly weaker than the standard port-numbering model has been studied since the 1990s, under various terms---see Table for a summary of terminology, and Table for an overview of the main differences in the research directions. Questions related to specific problems, models, and graph families have been studied previously, and indeed many of the techniques and ideas that we use are now standard---this includes the use of symmetry and isomorphisms, local views, covering graphs (lifts) and universal covering graphs, and factors and factorisations. Mayer, Naor, and Stockmeyer @cite_47 @cite_68 made it explicit that the parity of node degrees makes a huge difference in the port-numbering model, and Yamashita and Kameda @cite_45 discussed factors and factorisations in this context; the underlying graph-theoretic observations can be traced back to as far as Petersen's 1891 work @cite_35 . Some equivalences and separations between the classes are already known, or at least implicit in prior work---see, in particular, @cite_72 and Yamashita and Kameda @cite_10 .
@cite_35 @cite_72 @cite_45 @cite_47 @cite_68 @cite_10
164544547 2124068769 2017345786 2110664267
We consider the problem of electing a leader in an an-onymous network of processors. More precisely our modelis that of a directed graph, with vertices corresponding toprocessors, and arcs to communication links (we freely in-terchange symmetric digraphs and undirected graphs). Wemake no assumption on the structure of the network: self-loopsand parallel arcs are allowed. In particular, processorsare anonymous: they do not have unique identiﬁers.We consider both synchronous and asynchronous pro-cessor activation models, and models with and without“port awareness” (local names for outgoing and or for in-coming arcs). We consider both unidirectional and bidirec-tional links. Our models will be deﬁned precisely in thesequel.It is well known that once a leader is found, many other In anonymous networks, the processors do not have identity numbers. We investigate the following representative problems on anonymous networks: (a) the leader election problem, (b) the edge election problem, (c) the spanning tree construction problem, and (d) the topology recognition problem. On a given network, the above problems may or may not be solvable, depending on the amount of information about the attributes of the network made available to the processors. Some possibilities are: (1) no network attribute information at all is available, (2) an upper bound on the number of processors in the network is available, (3) the exact number of processors in the network is available, and (4) the topology of the network is available. In terms of a new graph property called "symmetricity", in each of the four cases (1)-(4) above, we characterize the class of networks on which each of the four problems (a)(d) is solvable. We then relate the symmetricity of a network to its 1- and 2-factors. The purpose of this paper is a study of computation that can be done locally in a distributed network, where "locally" means within time (or distance) independent of the size of the network. Locally checkable labeling (LCL) problems are considered, where the legality of a labeling can be checked locally (e.g., coloring). The results include the following: There are nontrivial LCL problems that have local algorithms. There is a variant of the dining philosophers problem that can be solved locally. Randomization cannot make an LCL problem local; i.e., if a problem has a local randomized algorithm then it has a local deterministic algorithm. It is undecidable, in general, whether a given LCL has a local algorithm. However, it is decidable whether a given LCL has an algorithm that operates in a given time @math . Any LCL problem that has a local algorithm has one that is order-invariant (the algorithm depends only on the order of the processor IDs). In the networks considered in this paper, processors do not have distinct identity numbers. On such a network, we discuss the leader election problem and the problem of counting the number of processors having the same identity number. As the communication mode, we consider port-to-port, broadcast-to-port, port-to-mail box, and broadcast-to-mailbox. For each of the above communication modes, we present: an algorithm for counting the number of processors with the same identity number; an algorithm for solving the leader election problem; and a graph theoretical characterization of the solvable class for the leader election problem.