# Distributed Turing Machine?

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) between TM.

• Possibly related: cstheory.stackexchange.com/questions/426/… – Jukka Suomela Apr 18 '11 at 14:56
• 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 Apr 18 '11 at 16:04
• @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 Apr 18 '11 at 17:54
• ok. that sounds reasonable. – Suresh Venkat Apr 18 '11 at 18:28
• 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 Apr 18 '11 at 18:52

[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 also used in Lynch's Distributed Computing book
2. Communicating Sequential Processes
3. Temporal logic of actions
4. Pi-Calculus (also already mentioned by Alex)
5. And more (have been and will be mentioned here)...
• 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 Apr 18 '11 at 18:07

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.

• Really interesting model :-). I'm going to read it this weekend. – Marcos Roriz Junior Apr 18 '11 at 18:00

I'm surprised that Petri Nets have not yet been mentioned! Extensions of Petri Nets like Coloured Petri Nets or Petri Nets with inhibitor arcs are Turing-complete.

• 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 Apr 21 '11 at 10:43
• Only Petri himself insisted on applying them to physical systems. They are mostly used to describe communicating software, business processes, etcetera. – reinierpost Mar 14 '12 at 15:06

(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).

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 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.

• 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 Apr 21 '11 at 14:19