1. About the efficiency of partial replication to implement Distributed Shared Memory
- Author
-
Alessia Milani, J.-M. Helary, Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), and Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome]
- Subjects
Theoretical computer science ,Distributed shared memory ,Computer science ,Distributed computing ,[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] ,duplication partielle ,Causal consistency ,algorithme de plus court chemin ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,shortest path algorithm ,consistency criterion ,cohérence causale ,0202 electrical engineering, electronic engineering, information engineering ,PRAM consistency ,partial replication ,cohérence PRAM ,Mémoire partagée répartie ,critères de cohérence ,Message passing ,Consistency model ,020202 computer hardware & architecture ,causal consistency ,010201 computation theory & mathematics ,Graph (abstract data type) ,Distributed memory - Abstract
Distributed Shared Memory abstraction (DSM) is traditionally realized through a distributed memory consistency system(MCS) on top of a message passing system. In this paper we analyze the impossibility of efficient partial replication implementation of causally consistent DSM. Efficiency is discussed in terms of control information that processes have to propagate to maintain consistency. We introduce the notions of share graph and hoop to model variable distribution and the concept of dependency chain to characterize processes that have to manage information about a variable even though they do not read or write that variable. Then, we weaken causal consistency to try to define new consistency criteria weaker enough to allow efficient partial replication implementations and strong enough to solve interesting problems. Finally, we prove that PRAM is such a criterion, and illustrate its power with the Bellman-Ford shortest path algorithm. / Les mémoires partagées réparties constituent une abstraction qui est traditionellement concrétisée par un système réparti de mémoire cohérente, au-dessus d'un système de communication par messages. Dans ce rapport, on analyse l'impossibilité d'avoir une implémentation efficace de mémoire partagée répartie à cohérence causale, basée sur la duplication partielle des variables. L'efficacité est envisagée en terme d'information contrôle qui doit être propagée pour assurer la cohérence. On introduit les notions de graphe de partage et d'arceau, qui modélisent la répartition des variables et la notion de chaîne de dépendance pour caractériser les processus qui doivent gérer des informations relatives à une variable dont ils ne possèdent pas de copie locale. Ensuite, on affaiblit le critère de cohérence causale, dans le but de déterminer un nouveau critère de cohérence qui soit suffisament faible pour permettre un implémentation efficace basée sur la duplication partielle, mais suffisament forte pour pouvoir résoudre des problèmes intéressants. Finalement, on prouve que le critère appelé PRAM satisfait ces exigences, et illustrons sa pertinence en montrant une implémentation de l'algorithme de plus court chemin de Bellman-Ford.
- Published
- 2005