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.
turing-machines
dc.distributed-comp
Marcos Roriz Junior
źródło
źródło
Odpowiedzi:
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 .
Myślę, że jest to całkowicie możliwe, ale nikt (o którym wiem) nie przyjrzał się temu. Wiem o nich:
źródło
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.
źródło
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.
źródło
( 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:
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.XX 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!TT 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).
źródło
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ę.
źródło