Machine de Turing distribuée?

Je suis un étudiant en master axé sur les systèmes distribués mais également intéressé par l'informatique théorique. Je me demandais s'il y avait une représentation formelle d'un système distribué au-dessus d'une machine de turing? Autrement dit, est-il possible d'étendre (faire une variante) le concept d'une machine de turing pour tirer parti de l'informatique distribuée?

Une idée est de créer une bande partagée (quelque chose de similaire à Tuple Space ) entre TM.

[Y a-t-il] une représentation formelle d'un système distribué au-dessus d'une machine de Turing?

À cet égard, la discussion (voir le lien publié par Jukka sur les commentaires) est la façon de regarder. La façon dont, je le vois, comment vous représenteriez officiellement un système distribué dépend en grande partie de la façon dont vous les voyez, et cela dépend de "vos hypothèses de système préférées" (c.-à-d. Les hypothèses sur la synchronie (c.-à-d. Le calendrier relatif des actions dans le système distribué)). système), sur la communication (passage de messages vs mémoire partagée), sur les défauts (de processus et / ou de liens, bénins ou byzantins, etc.). Comme la communauté n'est pas d'accord sur ce point, il n'y a pas non plus d'accord sur le formalisme de base .

[Est-il possible d'étendre (faire une variante) le concept d'une machine de turing pour tirer parti de l'informatique distribuée?

Je suppose que c'est tout à fait possible, mais personne (à ma connaissance) ne s'y est penché. Ce que je sais, ce sont:

1. Timed IO Automata également utilisé dans le livre de calcul distribué de Lynch
2. Communication des processus séquentiels
3. Logique temporelle des actions
4. Pi-Calculus (également déjà mentionné par Alex)
5. Et plus (ont été et seront mentionnés ici) ...

Vous voudrez peut-être examiner le Pi-Calcul.

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

C'est un calcul basé sur le traitement conçu pour raisonner sur les systèmes distribués.

Je suis surpris que Petri Nets n'ait pas encore été mentionné! Les extensions des réseaux de Petri comme les réseaux de Petri colorés ou les réseaux de Petri avec des arcs inhibiteurs sont Turing-complete.

( Avertissement: vues quelque peu biaisées, simplifications excessives et généralisations flagrantes à venir. )

Souvent, la différence entre l'informatique distribuée et l'informatique parallèle peut être résumée comme suit:

• En informatique distribuée , les principales mesures de complexité sont liées aux flux de communication et d' information : combien de tours de communication («temps»); combien de bits transmis.
• En informatique parallèle , les principales mesures de complexité sont liées au calcul et au traitement de l'information : combien d'étapes élémentaires ("temps"); combien de bits stockés.

Si vous adoptez cette perspective, il s'avère souvent que pour modéliser des systèmes distribués, peu importe le type de puissance de calcul dont disposent vos nœuds (ou processeurs ou ordinateurs).

$O(n)$

$X$$X$

$T$$T$

Par conséquent, utiliser les machines Turing comme point de départ pour modéliser des systèmes distribués me semble un peu contre nature: si c'est un aspect non pertinent, pourquoi tout construire par-dessus? En revanche, dans le calcul parallèle, cela serait naturel (sauf que le modèle est généralement quelque chose comme PRAM au lieu de machines de Turing).

Certains soutiennent qu'en fonction de votre point de vue, vous pourriez penser que les systèmes distribués sont quelque chose de plus puissant qu'une machine de Turing, en raison des différentes interprétations de la limitation du non-déterminisme et de l'équité. Ce lien a une discussion intéressante sur le sujet. Herlihy / Shavit dans leur livre "L'art de la programmation multiprocesseur" fait valoir que la calculabilité de Turing se réfère intrinsèquement à la notion d'un algorithme (séquentiel), et ne sont en quelque sorte pas appropriées pour raisonner sur l'informatique distribuée. Je dois mentionner que c'est discutable et controversé, donc j'espère que personne ne me jette des pierres parce que je dis cela.