Máquina de Turing distribuída?

10

Sou um estudante de mestrado focado em sistemas distribuídos, mas também interessado em ciência da computação teórica. Eu queria saber se existe uma representação formal de um sistema distribuído em cima de uma máquina de turing? Ou seja, é possível estender (criar uma variante) o conceito de uma máquina de turing para aproveitar a computação distribuída?

Uma idéia é fazer uma fita compartilhada (algo semelhante ao Tuple Space ) entre a TM.

Marcos Roriz Junior
fonte
8
Possivelmente relacionado: cstheory.stackexchange.com/questions/426/…
Jukka Suomela
3
a pergunta à qual o Jukka está vinculado pode responder sua pergunta não inteiramente. Se sim, talvez você possa encerrar este e, se não, talvez possa esclarecer o que é diferente?
Suresh Venkat
@Suresh Venkat, acho que a pergunta que Jukka vinculou definitivamente está no tópico, mas faça uma pergunta maior: "por que não existe um modelo padrão / aceitável para computação distribuída?". Minha pergunta definitivamente tem tudo a ver com essa, mas fiquei motivado a descobrir sobre / qualquer representação formal da computação distribuída.
Marcos Roriz Júnior
Está bem. isso parece razoável.
Suresh Venkat
2
A propósito, sua abordagem de "fita compartilhada" parece mais um modelo de computação paralela em vez de computação distribuída . Portanto, também pode fazer sentido olhar para os modelos usados ​​no campo da computação paralela (por exemplo, o modelo PRAM).
Jukka Suomela

Respostas:

10

[Existe] uma representação formal de um sistema distribuído em cima de uma máquina de turing?

Com relação a isso, a discussão (veja o link postado por Jukka nos comentários) é o caminho a seguir. A maneira como vejo formalmente como você representaria um sistema distribuído depende muito de como você os vê, e isso depende de "suas premissas favoritas do sistema" (ou seja, as premissas da sincronia) (ou seja, o tempo relativo das ações no sistema distribuído sistema), na comunicação (passagem de mensagem versus memória compartilhada), falhas (de processos e / ou links, benignos ou bizantinos, etc.) Como a comunidade não concorda com esse ponto, também não há acordo sobre o formalismo básico .

[É] possível estender (criar uma variante) o conceito de uma máquina de turing para tirar proveito da computação distribuída?

Eu acho que é inteiramente possível, mas ninguém (que eu conheça) investigou. O que eu sei são:

  1. Automated IO Automata também usado no livro Distributed Computing de Lynch
  2. Comunicação de processos sequenciais
  3. Lógica temporal de ações
  4. Pi-Calculus (também já mencionado por Alex)
  5. E mais (foram e serão mencionados aqui) ...
Martin B.
fonte
Obrigado pela explicação. O argumento que você fez sobre discórdias sobre como o modelo deve ser (sincronização, assíncrona etc.) definitivamente afeta a criação de um modelo padronizado. Ótimos links e obrigado por responder :-).
Marcos Roriz Júnior
6

Você pode querer examinar o Pi-Calculus.

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

É um cálculo baseado em processamento, projetado para raciocinar sobre sistemas distribuídos.

Alex Gonopolskiy
fonte
Modelo realmente interessante :-). Vou ler este fim de semana.
Marcos Roriz Junior
5

Estou surpreso que as redes de Petri ainda não tenham sido mencionadas! Extensões de redes de Petri como redes coloridas de Petri ou redes de Petri com arcos inibidores são completas em Turing.

Dai Le
fonte
As redes de Petri são um formalismo importante na simultaneidade, mas como sua motivação vem da tentativa de modelar determinado processo físico, elas não são realmente comparáveis ​​às MTs.
Charles Stewart
Somente o próprio Petri insistia em aplicá-los aos sistemas físicos. Eles são usados ​​principalmente para descrever software de comunicação, processos de negócios, etc.
Reinierpost
5

( Aviso: visões um tanto tendenciosas, simplificações excessivas e generalizações flagrantes à frente. )

Frequentemente, a diferença entre computação distribuída e computação paralela pode ser resumida da seguinte forma:

  • Na computação distribuída , as principais medidas de complexidade estão relacionadas aos fluxos de comunicação e informação : quantas rodadas de comunicação ("tempo"); quantos bits transmitidos.
  • Na computação paralela , as principais medidas de complexidade estão relacionadas ao processamento da computação e da informação : quantas etapas elementares ("tempo"); quantos bits armazenados.

Se você adota essa perspectiva, geralmente acontece que, para modelar sistemas distribuídos, não importa realmente que tipo de poder computacional seus nós (ou processadores ou computadores) possuem.

O(n)

XX

TT

Portanto, o uso de máquinas de Turing como ponto de partida para modelar sistemas distribuídos me parece um pouco natural: se esse é um aspecto irrelevante, por que construir tudo sobre ele? Por outro lado, na computação paralela isso seria natural (exceto que o modelo geralmente é algo como PRAM em vez de máquinas de Turing).

Jukka Suomela
fonte
3

Alguns argumentam que, dependendo da sua visão, você poderia pensar em sistemas distribuídos como algo mais poderoso que uma Máquina de Turing, devido a diferentes interpretações de limites do não-determinismo e da justiça. Este link tem uma discussão interessante sobre o tópico. Herlihy / Shavit, em seu livro "A arte da programação de multiprocessadores", argumenta que a computabilidade de Turing se refere inerentemente à noção de um algoritmo (seqüencial) e, em certo sentido, não é apropriada para raciocinar sobre a computação distribuída. Devo mencionar que isso é discutível e controverso, por isso espero que ninguém me atire porque estou dizendo isso.

Giovanni Funchal
fonte
11
Eu acho que a comparação não é muito apropriada. Simplesmente falando, no contexto das máquinas de Turing, o não determinismo é um recurso: refere-se à capacidade da máquina de seguir vários caminhos de execução simultaneamente, portanto é essencialmente uma forma de paralelismo. No contexto de sistemas distribuídos, o não-determinismo geralmente é mais um obstáculo: é usado para modelar as várias propriedades imprevisíveis dos sistemas distribuídos no mundo real, como falta de sincronização e falhas.
Antonio Valerio Miceli-Barone