Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algèbre de processus
Résumé
Les algèbres de processus sont une famille de langages formels permettant de modéliser les systèmes (informatiques) concurrents ou distribués. Les algèbres de processus fournissent des outils formels permettant principalement de caractériser les interactions entre processus au sein d'un système concurrent ou distribué, les interactions prenant la forme d'échanges de messages. L'étude des algèbres de processus relève de l'informatique théorique, et leurs applications relèvent principalement du génie logiciel, en particulier des systèmes distribués.
Les différents calculs peuvent se distinguer par différents points : calcul synchrone ou asynchrone, calcul du premier ordre ou d'ordre supérieur (dans le second cas, les messages échangés sont des processus), etc.
Les principaux algèbres de processus utilisés sont :
CSP (Communicating sequential processes) ;
CCS ;
LOTOS (Language Of Temporal Ordering Specification) - norme ISO 8807 ;
Pi-calcul.
La volonté de formaliser les systèmes concurrents se matérialise à la fin des années 1970 et au début des années 1980. Par exemple, Milner publie "A Calculus of Communicating Systems" en 1980, qui présente CCS. Dans son introduction, Milner indique que le développement de CCS s'inscrit dans la lignée du développement des réseaux de Petri présenté en 1962 et de CSP (1978).
Bien que les différentes algèbres comportent différentes constructions, des éléments de base (comme des primitives de communication ou de composition parallèle) se retrouvent au travers des différentes algèbres (avec parfois des différences subtiles).
Naturellement, les résultats et les caractéristiques de chaque algèbre dépendent des choix formels qui sont faits.
Les algèbres comprennent une notion de processus inactif ou terminé, qui caractérise un processus ne pouvant interagir avec le reste de l'environnement. Le plus souvent, ce processus est noté ou .
La composition séquentielle permet de composer des actions ordonnées. Par exemple, dans CCS, la composition séquentielle est notée , qui désigne un processus qui peut effectuer l'action , puis l'action .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Concepts associés (16)
Calculus of communicating systems
The calculus of communicating systems (CCS) is a process calculus introduced by Robin Milner around 1980 and the title of a book describing the calculus. Its actions model indivisible communications between exactly two participants. The formal language includes primitives for describing parallel composition, choice between actions and scope restriction. CCS is useful for evaluating the qualitative correctness of properties of a system such as deadlock or livelock.
Pi-calcul
Le Pi-calcul (ou π-calcul) est un langage de programmation théorique inventé par Robin Milner. Ce langage occupe dans le domaine de l'informatique parallèle et distribuée un rôle similaire à celui du λ-calcul dans l'informatique classique. En tant que langage de programmation théorique (ou langage formel), le π-calcul ne vise pas à permettre de construire des programmes exécutables.
Concurrency (computer science)
In computer science, concurrency is the ability of different parts or units of a program, algorithm, or problem to be executed out-of-order or in partial order, without affecting the outcome. This allows for parallel execution of the concurrent units, which can significantly improve overall speed of the execution in multi-processor and multi-core systems. In more technical terms, concurrency refers to the decomposability of a program, algorithm, or problem into order-independent or partially-ordered components or units of computation.