Verteilte Turingmaschine?

10

Ich bin ein Masterstudent, der sich auf verteilte Systeme konzentriert, sich aber auch für theoretische Informatik interessiert. Ich habe mich gefragt, ob es eine formale Darstellung eines verteilten Systems auf einer Turingmaschine gibt. Ist es also möglich, das Konzept einer Turingmaschine zu erweitern (eine Variante zu erstellen), um die Vorteile des verteilten Rechnens zu nutzen?

Eine Idee ist, ein gemeinsames Band (ähnlich wie Tuple Space ) zwischen TM zu erstellen .

Marcos Roriz Junior
quelle
8
Möglicherweise verwandt: cstheory.stackexchange.com/questions/426/…
Jukka Suomela
3
Die Frage, auf die Jukka verweist, könnte Ihre Frage nicht vollständig beantworten. Wenn ja, können Sie diesen vielleicht schließen, und wenn nicht, können Sie vielleicht klären, was anders ist?
Suresh Venkat
@Suresh Venkat, ich denke, dass die Frage, die Jukka verlinkt hat, definitiv zum Thema gehört, aber stellen Sie eine größere Frage: "Warum gibt es kein Standard- / akzeptables Modell für verteiltes Rechnen?". Meine Frage hat definitiv alles damit zu tun, aber ich war motiviert, etwas über die formale Darstellung von verteiltem Computing herauszufinden .
Marcos Roriz Junior
okay. das klingt vernünftig.
Suresh Venkat
2
Übrigens klingt Ihr "Shared Tape" -Ansatz eher wie ein Modell für paralleles Computing als für verteiltes Computing. Daher kann es auch sinnvoll sein, die im Bereich des parallelen Rechnens verwendeten Modelle (z. B. das PRAM-Modell) zu betrachten.
Jukka Suomela

Antworten:

10

[Gibt es] eine formale Darstellung eines verteilten Systems auf einer Turingmaschine?

Diesbezüglich ist die Diskussion (siehe Link, den Jukka zu Kommentaren gepostet hat) der richtige Weg. Die Art und Weise, wie Sie ein verteiltes System formal darstellen würden, hängt weitgehend davon ab, wie Sie sie anzeigen, und dies hängt von "Ihren bevorzugten Systemannahmen" ab (dh den Annahmen zur Synchronität (dh dem relativen Zeitpunkt der Aktionen im verteilten System) System), zur Kommunikation (Nachrichtenübermittlung vs. gemeinsamer Speicher), zu Fehlern (von Prozessen und / oder Verbindungen, gutartig oder byzantinisch usw.). Da sich die Community in diesem Punkt nicht einig ist, gibt es auch keine Einigung über den grundlegenden Formalismus .

[Ist] es möglich, das Konzept einer Turingmaschine zu erweitern (eine Variante zu erstellen), um die Vorteile des verteilten Rechnens zu nutzen?

Ich denke, es ist durchaus möglich, aber niemand (von dem ich weiß) hat sich damit befasst. Was ich weiß, sind diese:

  1. Zeitgesteuerte E / A-Automaten, die auch in Lynchs Distributed Computing-Buch verwendet werden
  2. Sequentielle Prozesse kommunizieren
  3. Zeitliche Logik der Handlungen
  4. Pi-Calculus (auch schon von Alex erwähnt)
  5. Und mehr (wurden und werden hier erwähnt) ...
Martin B.
quelle
Vielen Dank für die Erklärung. Der Punkt, den Sie über Zwietracht darüber gemacht haben, wie das Modell sein soll (Synchronisierung, Asynchronisierung usw.), wirkt sich definitiv auf die Erstellung eines standardisierten Modells aus. Tolle Links und danke für die Antwort :-).
Marcos Roriz Junior
6

Vielleicht möchten Sie sich mit Pi-Calculus befassen.

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

Es ist ein prozessbasierter Kalkül, der zum Nachdenken über verteilte Systeme entwickelt wurde.

Alex Gonopolskiy
quelle
Wirklich interessantes Modell :-). Ich werde es dieses Wochenende lesen.
Marcos Roriz Junior
5

Ich bin überrascht, dass Petri-Netze noch nicht erwähnt wurden! Erweiterungen von Petri-Netzen wie farbigen Petri-Netzen oder Petri-Netzen mit Inhibitor-Bögen sind Turing-vollständig.

Dai Le
quelle
Petri-Netze sind ein wichtiger Formalismus bei der Parallelität, aber da ihre Motivation darin besteht, bestimmte physikalische Prozesse zu modellieren, sind sie nicht wirklich mit TMs vergleichbar.
Charles Stewart
Nur Petri selbst bestand darauf, sie auf physikalische Systeme anzuwenden. Sie werden hauptsächlich zur Beschreibung von Kommunikationssoftware, Geschäftsprozessen usw. verwendet.
Reinierpost
5

( Warnung: etwas voreingenommene Ansichten, übermäßige Vereinfachungen und offensichtliche Verallgemeinerungen. )

Oft kann der Unterschied zwischen verteiltem und parallelem Rechnen wie folgt zusammengefasst werden:

  • Beim verteilten Rechnen beziehen sich die primären Komplexitätsmaße auf die Kommunikation und den Informationsfluss : wie viele Kommunikationsrunden ("Zeit"); wie viele Bits übertragen.
  • Beim parallelen Rechnen beziehen sich die primären Komplexitätsmaße auf die Berechnung und Informationsverarbeitung : wie viele Elementarschritte ("Zeit"); wie viele Bits gespeichert.

Wenn Sie diese Perspektive einnehmen, stellt sich häufig heraus, dass es für die Modellierung verteilter Systeme nicht wirklich darauf ankommt, über welche Rechenleistung Ihre Knoten (oder Prozessoren oder Computer) verfügen.

In der Regel können Sie einfach davon ausgehen, dass jeder Knoten nur eine Zustandsmaschine ist (häufig reicht es aus, eine relativ kleine Anzahl möglicher Zustände wie ). Das Gerät ändert seinen Status basierend auf den empfangenen Nachrichten. Normalerweise interessiert es Sie nicht so sehr, wie die Maschine ihren Zustand ändert. Es könnte eine Turing-Maschine sein, aber das ist nicht wirklich so relevant.O(n)

Wenn Sie beispielsweise ein (vernünftiges) Diagrammproblem und die verteilte Komplexität der Lösung von (z. B. die Anzahl der zur Lösung erforderlichen Kommunikationsrunden), wirkt sich die Art und Weise, wie Sie die Berechnung an jedem Knoten modellieren, normalerweise nicht auf die Antwort aus. Wenn Sie es zuerst mit Turing-Maschinen analysieren und dann ein beliebig mächtiges Orakel annehmen, ist die Antwort normalerweise dieselbe. Sie können uneinheitliche Ratschläge hinzufügen, die nichts ändern.X.XX

Der "Engpass" ist, dass Sie nicht schnell Informationen sammeln können. In Kommunikationsrunden kann jeder Knoten, unabhängig davon, was Sie tun, nur Informationen zu seiner eigenen Radius- Nachbarschaft haben. Sie könnten an jedem Knoten einen beliebig leistungsfähigen Prozessor haben, aber was nützt es, wenn die Prozessoren keine zu verarbeitenden Informationen haben!T.TT

Daher klingt es für mich etwas unnatürlich, Turing-Maschinen als Ausgangspunkt für die Modellierung verteilter Systeme zu verwenden: Wenn dies ein irrelevanter Aspekt ist, warum alles darauf aufbauen? Auf der anderen Seite wäre dies beim parallelen Rechnen natürlich (außer dass das Modell normalerweise so etwas wie PRAM anstelle von Turing-Maschinen ist).

Jukka Suomela
quelle
3

Einige argumentieren , dass je nach Standpunkt, Sie von verteilten Systemen als etwas einfiel mehr mächtiger als eine Turing - Maschine, wegen der unterschiedlichen Interpretationen der Beschränktheit von Nicht-Determinismus und Fairness. Dieser Link hat eine interessante Diskussion zum Thema. Herlihy / Shavit argumentieren in ihrem Buch "Die Kunst der Multiprozessor-Programmierung", dass die Berechenbarkeit von Turing von Natur aus auf den Begriff eines (sequentiellen) Algorithmus verweist und in gewissem Sinne nicht geeignet ist, über verteiltes Rechnen nachzudenken. Ich sollte erwähnen, dass dies fraglich und kontrovers ist, also hoffe ich, dass mir niemand Steine ​​wirft, weil ich das sage.

Giovanni Funchal
quelle
1
Ich denke, der Vergleich ist nicht sehr angemessen. Einfach ausgedrückt ist Nichtdeterminismus im Kontext von Turing-Maschinen eine Ressource: Er bezieht sich auf die Fähigkeit der Maschine, mehrere Ausführungspfade gleichzeitig zu verfolgen, daher handelt es sich im Wesentlichen um eine Form der Parallelität. Im Kontext verteilter Systeme ist Nichtdeterminismus normalerweise eher ein Hindernis: Er wird verwendet, um die verschiedenen unvorhersehbaren Eigenschaften realer verteilter Systeme wie fehlende Synchronisation und Fehler zu modellieren.
Antonio Valerio Miceli-Barone