<p>You might want to look into Pi-Calculus.</p>

<p><a href="http://en.wikipedia.org/wiki/%CE%A0-calculus">http://en.wikipedia.org/wiki/%CE%A0-calculus</a></p>

<p>Its a processed based calculus designed for reasoning about distributed systems.</p>

CC BY-SA 3.0
2011-04-18T18:00:04.763Z
Really interesting model :-). I'm going to read it this weekend.
Marcos Roriz Junior
CC BY-SA 3.0
2011-04-18T16:39:00.337Z
2011-04-18T16:39:00.337Z
Alex Gonopolskiy
<p>I'm surprised that <a href="http://en.wikipedia.org/wiki/Petri_net">Petri Nets</a> have not yet been mentioned! Extensions of Petri Nets like <em><a href="http://cs.au.dk/fileadmin/site_files/cs/research_areas/centers_and_projects/sttt2007.pdf">Coloured Petri Nets</a></em> or <em>Petri Nets with inhibitor arcs</em> are Turing-complete.</p>

CC BY-SA 3.0
2011-04-21T10:43:22.903Z
Petri nets are an important formalism in concurrency, but as their motivation comes from trying to model certain physical process, they aren't really comparable to TMs.
Charles Stewart
CC BY-SA 3.0
2012-03-14T15:06:25.653Z
Only Petri himself insisted on applying them to physical systems.  They are mostly used to describe communicating software, business processes, etcetera.
reinierpost
CC BY-SA 3.0
2011-04-19T23:53:05.327Z
2011-04-19T23:53:05.327Z
Dai Le
<p>(<em>Warning: somewhat biased views, oversimplifications, and blatant generalisations ahead.</em>)</p>

<p>Often the difference between distributed computing and parallel computing can be summarised as follows:</p>

<ul>
<li>In <strong>distributed</strong> computing, the primary complexity measures are related to <strong>communication</strong> and <em>information flows</em>: how many communication rounds ("time"); how many bits transmitted.</li>
<li>In <strong>parallel</strong> computing, the primary complexity measures are related to <strong>computation</strong> and <em>information processing</em>: how many elementary steps ("time"); how many bits stored.</li>
</ul>

<p>If you take this perspective, then it often turns out that in order to model distributed systems, it does not really matter that what kind of <em>computational</em> power your nodes (or processors or computers) happen to have.</p>

<p>Typically, you can simply assume that each node is just a state machine (often it is enough to have a reasonably small number of possible states, such as $O(n)$). The machine changes its state based on the messages it receives. Usually you are not that interested in <em>how</em> the machine changes its state. It might be a Turing machine, but this is not really that relevant.</p>

<p>For example, if you take a (reasonable) graph problem $X$ and study the distributed complexity of solving $X$ (e.g., the number of communication rounds required to solve it), the way you model computation at each node does not usually affect the answer. If you analyse it first by using Turing machines, and then by assuming an arbitrarily powerful oracle, the answer is typically the same. You can add non-uniform advice and it does not change anything.</p>

<p>The "bottleneck" is that you cannot gather information quickly. In $T$ communication rounds, no matter what you do, each node can only have information regarding its own radius-$T$ neighbourhood. You could have an arbitrarily powerful processor at each node, but what good does it do if the processors do not have any information to process!</p>

<p>Hence using Turing machines as the <em>starting point</em> in order to model distributed systems sounds a bit unnatural to me: if this is an irrelevant aspect, why build everything on top of it? On the other hand, in parallel computing this would be natural (except that the model is usually something like PRAM instead of Turing machines).</p>

CC BY-SA 3.0
2011-04-20T12:36:36.163Z
2011-04-20T12:36:36.163Z
Jukka Suomela
<p>Some argue that depending on your view, you could think of distributed systems as something <strong>more</strong> powerful than a Turing Machine, because of different interpretations of boundedness of non-determinism and fairness. <a href="http://lambda-the-ultimate.org/node/4140" rel="nofollow">This link</a> has an interesting discussion on the topic. Herlihy/Shavit in their book "The art of multiprocessor programming" argue that Turing computability inherently refers to the notion of a (sequential) algorithm, and are in some sense not appropriate for reasoning about distributed computing. I should mention that this is arguable and controversial so I hope no one throws me stones because I'm saying this.</p>

CC BY-SA 3.0
2011-04-21T14:19:55.720Z
I think the comparison is not very appropriate. Simply speaking, in the context of Turing machines, non-determinism is a resource: it refers to the ability of the machine to follow multiple execution path simultaneously, hence it's essentially a form of parallelism. In the context of distributed systems, instead, non-determinism is usually more an hindrance: it is used to model the various unpredictable properties of real-world distributed systems, such as lack of synchronization and failures.
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-04-20T11:47:14.820Z
2011-04-20T11:47:14.820Z
Giovanni Funchal
<blockquote>
  <p>[Is there] a formal representation of
  a distributed system on top of a
  turing machine? </p>
</blockquote>

<p>Regarding this, the discussion (see link posted by Jukka on comments) is the way to look. The way, I see it, how you would formally represent a distributed system largely depends on how you view them, and that depends on "your favourite system assumptions" (i.e., the assumptions on synchrony (i.e., relative timing of actions in the distributed system), on communication (message passing vs. shared memory), on faults (of processes and/or links, benign or Byzantine, etc). As the community does not agree on this point, there is also no agreement on the basic formalism.</p>

<blockquote>
  <p>[Is] it
  possible to extend (make a variant)
  the concept of a turing machine to
  take advantage of distributed
  computing?</p>
</blockquote>

<p>I guess it is entirely possible, but no-one (that I know of) has looked into it. 
What I know of are these:</p>

<ol>
<li><a href="http://groups.csail.mit.edu/tds/papers/Kirli/mainfinal.pdf">Timed IO Automata</a> also used in Lynch's Distributed Computing book </li>
<li><a href="http://en.wikipedia.org/wiki/Communicating_sequential_processes">Communicating Sequential Processes</a> </li>
<li><a href="http://en.wikipedia.org/wiki/Temporal_logic_of_actions">Temporal logic of actions</a></li>
<li><a href="http://en.wikipedia.org/wiki/%CE%A0-calculus">Pi-Calculus</a> (also already mentioned by Alex)</li>
<li>And more (have been and will be mentioned here)...</li>
</ol>

CC BY-SA 3.0
2011-04-18T18:07:11.000Z
Thank you for the explanation. The point that you made about discords on how the model should be (sync, async, etc) definitely impact the creation of a standardized model. Great links, and thanks for answering :-).
Marcos Roriz Junior
CC BY-SA 3.0
2011-04-18T17:46:50.807Z
2011-04-18T17:46:50.807Z
Martin B.
<p>I'm a master student focused on distributed systems but also interested on theoretical computer science. I was wondering if there is a formal representation of a distributed system on top of a turing machine? That is, is it possible to extend (make a variant) the concept of a turing machine to take advantage of distributed computing?</p>

<p>One idea, is to make a shared tape (something similar to <a href="http://en.wikipedia.org/wiki/Tuple_space">Tuple Space</a>) between TM.</p>

CC BY-SA 3.0
2011-04-18T14:56:47.027Z
Possibly related: http://cstheory.stackexchange.com/questions/426/why-have-we-not-been-able-to-develop-a-unified-complexity-theory-of-distributed-c
Jukka Suomela
CC BY-SA 3.0
2011-04-18T16:04:16.240Z
the question Jukka links to might answer your question not entirely. If so, maybe you can close this one, and if not, maybe you can clarify what's different ?
Suresh Venkat
CC BY-SA 3.0
2011-04-18T17:54:06.823Z
@Suresh Venkat, I think that the question Jukka linked is definitely on topic, but ask a bigger question: "why is there no standard/acceptable model for distributed computing?". My question definitely has everything to do with that one, but I was motivated to find about *the/any* formal representation of distributed computing.
Marcos Roriz Junior
CC BY-SA 3.0
2011-04-18T18:28:38.980Z
ok. that sounds reasonable.
Suresh Venkat
CC BY-SA 3.0
2011-04-18T18:52:37.717Z
By the way, your "shared tape" approach sounds more like a model of *parallel* computing instead of *distributed* computing. Therefore it might also make sense to look at the models used in the field of parallel computing (e.g., the PRAM model).
Jukka Suomela
<turing-machines><dc.distributed-comp>
Distributed Turing Machine?
Marcos Roriz Junior
# Distributed Turing Machine?

(Asked by: username_0 on 2011-04-18)

I'm a master student focused on distributed systems but also interested on theoretical computer science. I was wondering if there is a formal representation of a distributed system on top of a turing machine? That is, is it possible to extend (make a variant) the concept of a turing machine to take advantage of distributed computing?

One idea, is to make a shared tape (something similar to [Tuple Space](http://en.wikipedia.org/wiki/Tuple_space)) between TM.

**Tags:** turing-machines, dc.distributed-comp
> **Comments:**
> **username_1**: Possibly related: http://cstheory.stackexchange.com/questions/426/why-have-we-not-been-able-to-develop-a-unified-complexity-theory-of-distributed-c  
> **username_2**: the question Jukka links to might answer your question not entirely. If so, maybe you can close this one, and if not, maybe you can clarify what's different ?  
> **username_0**: @Suresh Venkat, I think that the question Jukka linked is definitely on topic, but ask a bigger question: "why is there no standard/acceptable model for distributed computing?". My question definitely has everything to do with that one, but I was motivated to find about *the/any* formal representation of distributed computing.  
> **username_2**: ok. that sounds reasonable.  
> **username_1**: By the way, your "shared tape" approach sounds more like a model of *parallel* computing instead of *distributed* computing. Therefore it might also make sense to look at the models used in the field of parallel computing (e.g., the PRAM model).  

---

## 5 answers

### Answer by username_9 on 2011-04-18. Score: 11 | Accepted answer

> [Is there] a formal representation of
> a distributed system on top of a
> turing machine?

Regarding this, the discussion (see link posted by Jukka on comments) is the way to look. The way, I see it, how you would formally represent a distributed system largely depends on how you view them, and that depends on "your favourite system assumptions" (i.e., the assumptions on synchrony (i.e., relative timing of actions in the distributed system), on communication (message passing vs. shared memory), on faults (of processes and/or links, benign or Byzantine, etc). As the community does not agree on this point, there is also no agreement on the basic formalism.

> [Is] it
> possible to extend (make a variant)
> the concept of a turing machine to
> take advantage of distributed
> computing?

I guess it is entirely possible, but no-one (that I know of) has looked into it.
What I know of are these:

1. [Timed IO Automata](http://groups.csail.mit.edu/tds/papers/Kirli/mainfinal.pdf) also used in Lynch's Distributed Computing book
2. [Communicating Sequential Processes](http://en.wikipedia.org/wiki/Communicating_sequential_processes)
3. [Temporal logic of actions](http://en.wikipedia.org/wiki/Temporal_logic_of_actions)
4. [Pi-Calculus](http://en.wikipedia.org/wiki/%CE%A0-calculus) (also already mentioned by Alex)
5. And more (have been and will be mentioned here)...

> **Comments:**
> **username_0**: Thank you for the explanation. The point that you made about discords on how the model should be (sync, async, etc) definitely impact the creation of a standardized model. Great links, and thanks for answering :-).  

---

### Answer by username_3 on 2011-04-18. Score: 6

You might want to look into Pi-Calculus.

<http://en.wikipedia.org/wiki/%CE%A0-calculus>

Its a processed based calculus designed for reasoning about distributed systems.

> **Comments:**
> **username_0**: Really interesting model :-). I'm going to read it this weekend.  

---

### Answer by username_4 on 2011-04-19. Score: 5

I'm surprised that [Petri Nets](http://en.wikipedia.org/wiki/Petri_net) have not yet been mentioned! Extensions of Petri Nets like *[Coloured Petri Nets](http://cs.au.dk/fileadmin/site_files/cs/research_areas/centers_and_projects/sttt2007.pdf)* or *Petri Nets with inhibitor arcs* are Turing-complete.

> **Comments:**
> **username_5**: Petri nets are an important formalism in concurrency, but as their motivation comes from trying to model certain physical process, they aren't really comparable to TMs.  
> **username_6**: Only Petri himself insisted on applying them to physical systems.  They are mostly used to describe communicating software, business processes, etcetera.  

---

### Answer by username_1 on 2011-04-20. Score: 5

(*Warning: somewhat biased views, oversimplifications, and blatant generalisations ahead.*)

Often the difference between distributed computing and parallel computing can be summarised as follows:

* In **distributed** computing, the primary complexity measures are related to **communication** and *information flows*: how many communication rounds ("time"); how many bits transmitted.
* In **parallel** computing, the primary complexity measures are related to **computation** and *information processing*: how many elementary steps ("time"); how many bits stored.

If you take this perspective, then it often turns out that in order to model distributed systems, it does not really matter that what kind of *computational* power your nodes (or processors or computers) happen to have.

Typically, you can simply assume that each node is just a state machine (often it is enough to have a reasonably small number of possible states, such as $O(n)$). The machine changes its state based on the messages it receives. Usually you are not that interested in *how* the machine changes its state. It might be a Turing machine, but this is not really that relevant.

For example, if you take a (reasonable) graph problem $X$ and study the distributed complexity of solving $X$ (e.g., the number of communication rounds required to solve it), the way you model computation at each node does not usually affect the answer. If you analyse it first by using Turing machines, and then by assuming an arbitrarily powerful oracle, the answer is typically the same. You can add non-uniform advice and it does not change anything.

The "bottleneck" is that you cannot gather information quickly. In $T$ communication rounds, no matter what you do, each node can only have information regarding its own radius-$T$ neighbourhood. You could have an arbitrarily powerful processor at each node, but what good does it do if the processors do not have any information to process!

Hence using Turing machines as the *starting point* in order to model distributed systems sounds a bit unnatural to me: if this is an irrelevant aspect, why build everything on top of it? On the other hand, in parallel computing this would be natural (except that the model is usually something like PRAM instead of Turing machines).


---

### Answer by username_7 on 2011-04-20. Score: 3

Some argue that depending on your view, you could think of distributed systems as something **more** powerful than a Turing Machine, because of different interpretations of boundedness of non-determinism and fairness. [This link](http://lambda-the-ultimate.org/node/4140) has an interesting discussion on the topic. Herlihy/Shavit in their book "The art of multiprocessor programming" argue that Turing computability inherently refers to the notion of a (sequential) algorithm, and are in some sense not appropriate for reasoning about distributed computing. I should mention that this is arguable and controversial so I hope no one throws me stones because I'm saying this.

> **Comments:**
> **username_8**: I think the comparison is not very appropriate. Simply speaking, in the context of Turing machines, non-determinism is a resource: it refers to the ability of the machine to follow multiple execution path simultaneously, hence it's essentially a form of parallelism. In the context of distributed systems, instead, non-determinism is usually more an hindrance: it is used to model the various unpredictable properties of real-world distributed systems, such as lack of synchronization and failures.  

---

