Rozproszona maszyna Turinga?

10

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.

Marcos Roriz Junior
źródło
8
Możliwe powiązanie: cstheory.stackexchange.com/questions/426/…
Jukka Suomela
3
pytanie, do którego prowadzi Jukka, może nie odpowiedzieć całkowicie na twoje pytanie. Jeśli tak, może możesz to zamknąć, a jeśli nie, może wyjaśnić, co jest inne?
Suresh Venkat
@Suresh Venkat, myślę, że pytanie, które łączy Jukka, zdecydowanie dotyczy tematu, ale zadaj większe pytanie: „dlaczego nie ma standardowego / akceptowalnego modelu dla przetwarzania rozproszonego?”. Moje pytanie z pewnością ma wszystko wspólnego z tym pytaniem, ale byłem zmotywowany, aby znaleźć / formalne przedstawienie przetwarzania rozproszonego.
Marcos Roriz Junior
ok. to brzmi rozsądnie.
Suresh Venkat
2
Nawiasem mówiąc, twoje podejście do współdzielonej taśmy brzmi bardziej jak model obliczeń równoległych zamiast obliczeń rozproszonych . Dlatego sensowne może być spojrzenie na modele stosowane w dziedzinie obliczeń równoległych (np. Model PRAM).
Jukka Suomela,

Odpowiedzi:

10

[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) ...
Martin B.
źródło
Dziękuję za wyjaśnienie. Wskazane przez ciebie dyskordowanie na temat tego, jaki powinien być model (synchronizacja, asynchronizacja itp.) Zdecydowanie wpływa na tworzenie standardowego modelu. Świetne linki i dziękuję za odpowiedź :-).
Marcos Roriz Junior
6

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.

Alex Gonopolskiy
źródło
Naprawdę ciekawy model :-). Przeczytam to w ten weekend.
Marcos Roriz Junior
5

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.

Dai Le
źródło
Sieci Petriego są ważnym formalizmem w współbieżności, ale ponieważ ich motywacja pochodzi z próby modelowania określonego procesu fizycznego, nie są one tak naprawdę porównywalne z bazami TM.
Charles Stewart
Tylko sam Petri nalegał na zastosowanie ich w systemach fizycznych. Są one najczęściej używane do opisywania oprogramowania komunikacyjnego, procesów biznesowych itp.
reinierpost
5

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

„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!TTT

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

Jukka Suomela
źródło
3

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

Giovanni Funchal
źródło
1
Myślę, że porównanie nie jest zbyt odpowiednie. Mówiąc najprościej, w kontekście maszyn Turinga niedeterminizm jest zasobem: odnosi się do zdolności maszyny do jednoczesnego podążania wieloma ścieżkami wykonania, a zatem jest zasadniczo formą równoległości. Natomiast w kontekście systemów rozproszonych niedeterminizm jest zwykle bardziej przeszkodą: służy do modelowania różnych nieprzewidywalnych właściwości rzeczywistych systemów rozproszonych, takich jak brak synchronizacji i awarie.
Antonio Valerio Miceli-Barone