Rozproszona maszyna Turinga?

Jestem studentem specjalizującym się w systemach rozproszonych, ale interesuję się również informatyką teoretyczną. Zastanawiałem się, czy istnieje formalna reprezentacja systemu rozproszonego na maszynie Turinga? To znaczy, czy można rozszerzyć (stworzyć wariant) koncepcję maszyny Turinga, aby skorzystać z przetwarzania rozproszonego?

Jednym z pomysłów jest utworzenie wspólnej taśmy (coś podobnego do Tuple Space ) między TM.

[Czy jest] formalna reprezentacja systemu rozproszonego na maszynie Turinga?

W związku z tym dyskusja (patrz link opublikowany przez Jukkę w komentarzach) jest sposobem na spojrzenie. Widzę, że sposób, w jaki formalnie reprezentowałbyś system rozproszony, zależy w dużej mierze od tego, jak go widzisz, a to zależy od „twoich ulubionych założeń systemowych” (tj. Założeń dotyczących synchronizacji (tj. Względnego czasu działań w rozproszonym system), komunikacji (przekazywanie wiadomości a pamięć współdzielona), błędów (procesów i / lub łączy, łagodnych lub bizantyjskich itp.) Ponieważ społeczność nie zgadza się w tej kwestii, nie ma również zgody co do podstawowego formalizmu .

[Czy] można rozszerzyć (stworzyć wariant) koncepcję maszyny Turinga, aby skorzystać z przetwarzania rozproszonego?

Myślę, że jest to całkowicie możliwe, ale nikt (o którym wiem) nie przyjrzał się temu. Wiem o nich:

1. Automaty czasowe IO wykorzystywane również w książce Lynch's Distributed Computing
2. Komunikowanie procesów sekwencyjnych
3. Tymczasowa logika działań
4. Pi-Calculus (również wspomniany już przez Alexa)
5. I więcej (były i zostaną wymienione tutaj) ...

Możesz przyjrzeć się Pi-Calculus.

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

Jest to rachunek oparty na przetwarzaniu przeznaczony do wnioskowania o systemach rozproszonych.

Dziwi mnie, że sieci Petriego nie zostały jeszcze wspomniane! Rozszerzenia sieci Petriego, takich jak kolorowe sieci Petriego lub sieci Petriego z łukami inhibitora, są kompletne w Turinga.

( Ostrzeżenie: nieco stronnicze poglądy, nadmierne uproszczenia i rażące uogólnienia przed nami ).

Często różnicę między obliczeniami rozproszonymi a obliczeniami równoległymi można podsumować w następujący sposób:

• W obliczeniach rozproszonych podstawowe miary złożoności odnoszą się do komunikacji i przepływów informacji : ile rund komunikacji („czas”); ile bitów przesłano.
• W obliczeniach równoległych podstawowe miary złożoności związane są z obliczeniami i przetwarzaniem informacji : ile podstawowych etapów („czas”); ile przechowywanych bitów.

Jeśli weźmiesz tę perspektywę, często okazuje się, że aby modelować systemy rozproszone, tak naprawdę nie ma znaczenia, jaką moc obliczeniową mają twoje węzły (procesory lub komputery).

Zazwyczaj można po prostu założyć, że każdy węzeł jest tylko maszyną stanu (często wystarczy mieć stosunkowo niewielką liczbę możliwych stanów, takich jak ). Urządzenie zmienia swój stan na podstawie otrzymanych wiadomości. Zwykle nie interesuje Cię, jak maszyna zmienia swój stan. Może to być maszyna Turinga, ale tak naprawdę nie jest to tak istotne.$O(n)$

Na przykład, jeśli weźmiesz (rozsądny) problem z grafem i przestudiujesz rozproszoną złożoność rozwiązania (np. Liczbę rund komunikacji wymaganych do jego rozwiązania), sposób modelowania obliczeń w każdym węźle zwykle nie wpływa na odpowiedź. Jeśli najpierw przeanalizujesz go za pomocą maszyn Turinga, a następnie przyjmując arbitralnie potężną wyrocznię, odpowiedź jest zwykle taka sama. Możesz dodać niejednolitą poradę, która niczego nie zmienia.$X$$X$

„Wąskim gardłem” jest to, że nie można szybko zebrać informacji. W rundach komunikacyjnych , bez względu na to, co robisz, każdy węzeł może mieć tylko informacje dotyczące własnego sąsiedztwa w promieniuMożesz mieć arbitralnie wydajny procesor w każdym węźle, ale co to za korzyść, jeśli procesory nie mają żadnych informacji do przetworzenia!$T$$T$

Dlatego używanie maszyn Turinga jako punktu wyjścia do modelowania systemów rozproszonych brzmi dla mnie trochę nienaturalnie: jeśli jest to nieistotny aspekt, po co budować na nim wszystko? Z drugiej strony, w obliczeniach równoległych byłoby to naturalne (z wyjątkiem tego, że model jest zwykle czymś w rodzaju PRAM zamiast maszyn Turinga).

Niektórzy twierdzą, że w zależności od widoku, można myśleć o systemach rozproszonych jako coś bardziej potężny niż maszyny Turinga, z powodu różnych interpretacji ograniczoności braku determinizmu i uczciwości. Ten link zawiera interesującą dyskusję na ten temat. Herlihy / Shavit w swojej książce „Sztuka programowania wieloprocesorowego” argumentują, że obliczalność Turinga nieodłącznie odnosi się do pojęcia algorytmu (sekwencyjnego) i jest w pewnym sensie nieodpowiednia do rozumowania na temat przetwarzania rozproszonego. Powinienem wspomnieć, że jest to dyskusyjne i kontrowersyjne, więc mam nadzieję, że nikt nie rzuca mi kamieni, ponieważ to mówię.