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.

Toward Distributed Computability Theory

Roberto Gorrieri
2019

Abstract

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.
Carl Adam Petri: Ideas, Personality, Impact
141
146
Roberto Gorrieri
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/714791
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact