Toward Distributed Computability Theory

Classic computability theory is based on sequential models of computation, like Turing machines [21, 5, 12]. It is sometimes argued that Turingcomplete models of computations are equally expressive. However, we argue that there are problems in distributed computing, such as the Last Man Standing problem [22, 9], that are not solvable in the Turing-complete model CCS(25,12)[10], while they are solvable within finite, nonpermissive [9] Petri nets, a class of nets extending conservatively finite Petri nets with inhibitor arcs. Hence, we argue that Petri nets, in their many facets, are more suitable than sequential models of computation to assess the relative expressive power of different languages for distributed systems. In doing so, we put the basis for distributed computability theory, as a generalization of sequential (or Turing) computability theory.