12
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 8
    $\begingroup$ Possibly related: cstheory.stackexchange.com/questions/426/… $\endgroup$
    – Jukka Suomela
    Commented Apr 18, 2011 at 14:56
  • 3
    $\begingroup$ 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 ? $\endgroup$
    – Suresh Venkat
    Commented Apr 18, 2011 at 16:04
  • $\begingroup$ @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. $\endgroup$
    – Marcos Roriz Junior
    Commented Apr 18, 2011 at 17:54
  • $\begingroup$ ok. that sounds reasonable. $\endgroup$
    – Suresh Venkat
    Commented Apr 18, 2011 at 18:28
  • 2
    $\begingroup$ 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). $\endgroup$
    – Jukka Suomela
    Commented Apr 18, 2011 at 18:52

5 Answers 5

Reset to default
11
$\begingroup$

[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)...
Improve this answer
$\endgroup$
1
  • $\begingroup$ 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 :-). $\endgroup$
    – Marcos Roriz Junior
    Commented Apr 18, 2011 at 18:07
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Really interesting model :-). I'm going to read it this weekend. $\endgroup$
    – Marcos Roriz Junior
    Commented Apr 18, 2011 at 18:00
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Charles Stewart
    Commented Apr 21, 2011 at 10:43
  • $\begingroup$ Only Petri himself insisted on applying them to physical systems. They are mostly used to describe communicating software, business processes, etcetera. $\endgroup$
    – reinierpost
    Commented Mar 14, 2012 at 15:06
5
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Antonio Valerio Miceli-Barone
    Commented Apr 21, 2011 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.