Anne Jaigu
07-25-2004, 02:49 AM
PI-1581: A Coherence Protocol for Cached Copies of Volatile
Objects in Peer-to-Peer Systems
Louis Rilling, Christine Morin
http://www.irisa.fr/bibli/publi/pi/2003/1581/1581.html
25 pages - décembre 2003
Abstract
We consider the problem of executing distributed applications using the
shared memory paradigm on dynamic and large scale distributed systems,
such as structured peer-to-peer systems. The shared memory is private to
an application, volatile, and components of the application
transparently access shared memory objects via their usual address
space. The peer-to-peer system tolerates up to f simultaneous
reconfiguration events (node failure, disconnection, or join) and an
infinite number of reconfigurations. We give a coherence protocol
similar to K. Li's protocols for cached copies of memory objects. The
protocol uses the peer-to-peer architecture to handle up to f
simultaneous reconfiguration events and an infinite number of
reconfigurations with a fail-stop/recovery model. Failures are tolerated
using backward error recovery and replicated automata to avoid restarts
of applications when possible. We prove that the protocol ensures
coherence of cached copies of memory objects despite reconfiguration
events, and ensures liveness if communications are reliable.
Résumé
Nous considérons le problème consistant à exécuter des applications
distribuées utilisant le paradigme de la mémoire partagée sur des
systèmes distribués dynamiques et de grande échelle, tels les systèmes
pair-à-pair structurés. La mémoire partagée n'est accessible que par une
application, elle est volatile, et les composants de l'application y
accèdent de manière transparente via leur espace d'adressage usuel. Le
système pair-à-pair tolère jusqu'à f événements de reconfiguration
(défaillance d'un noeud, déconnection, ou connection) simultanément, et
une infinité de reconfigurations. Nous donnons un protocole de cohérence
séquentielle similaire aux protocoles de K. Li pour des copies en cache
d'objets en mémoire. Le protocole utilise l'architecture pair-à-pair
pour gérer jusqu'à f événements de reconfiguration simultanément, et une
infinité de reconfigurations, en prenant un modèle défaillance
silencieuses avec recouvrements. Les défaillances sont tolérées en
utilisant des recouvrements en arrière et des automates dupliqués pour
éviter au possible de redémarrer les applications. Nous prouvons que le
protocole assure la cohérence séquentielle des copies en cache d'objets
en mémoire malgré l'occurrence d'événements de reconfiguration, et
assure la vivacité si les communication sont fiables.
Keywords: Fault-Tolerant Distributed Shared Memory, Self-Organizing
Distributed Systems, Structured Peer-to-Peer Systems, Checkpointing,
Replicated Automata
Mots clefs: Mémoire distribuée virtuellement partagée tolérante aux
fautes, systèmes distribués auto-gérés, systèmes pair-à-pair structurés,
points de reprise, automates dupliqués
Objects in Peer-to-Peer Systems
Louis Rilling, Christine Morin
http://www.irisa.fr/bibli/publi/pi/2003/1581/1581.html
25 pages - décembre 2003
Abstract
We consider the problem of executing distributed applications using the
shared memory paradigm on dynamic and large scale distributed systems,
such as structured peer-to-peer systems. The shared memory is private to
an application, volatile, and components of the application
transparently access shared memory objects via their usual address
space. The peer-to-peer system tolerates up to f simultaneous
reconfiguration events (node failure, disconnection, or join) and an
infinite number of reconfigurations. We give a coherence protocol
similar to K. Li's protocols for cached copies of memory objects. The
protocol uses the peer-to-peer architecture to handle up to f
simultaneous reconfiguration events and an infinite number of
reconfigurations with a fail-stop/recovery model. Failures are tolerated
using backward error recovery and replicated automata to avoid restarts
of applications when possible. We prove that the protocol ensures
coherence of cached copies of memory objects despite reconfiguration
events, and ensures liveness if communications are reliable.
Résumé
Nous considérons le problème consistant à exécuter des applications
distribuées utilisant le paradigme de la mémoire partagée sur des
systèmes distribués dynamiques et de grande échelle, tels les systèmes
pair-à-pair structurés. La mémoire partagée n'est accessible que par une
application, elle est volatile, et les composants de l'application y
accèdent de manière transparente via leur espace d'adressage usuel. Le
système pair-à-pair tolère jusqu'à f événements de reconfiguration
(défaillance d'un noeud, déconnection, ou connection) simultanément, et
une infinité de reconfigurations. Nous donnons un protocole de cohérence
séquentielle similaire aux protocoles de K. Li pour des copies en cache
d'objets en mémoire. Le protocole utilise l'architecture pair-à-pair
pour gérer jusqu'à f événements de reconfiguration simultanément, et une
infinité de reconfigurations, en prenant un modèle défaillance
silencieuses avec recouvrements. Les défaillances sont tolérées en
utilisant des recouvrements en arrière et des automates dupliqués pour
éviter au possible de redémarrer les applications. Nous prouvons que le
protocole assure la cohérence séquentielle des copies en cache d'objets
en mémoire malgré l'occurrence d'événements de reconfiguration, et
assure la vivacité si les communication sont fiables.
Keywords: Fault-Tolerant Distributed Shared Memory, Self-Organizing
Distributed Systems, Structured Peer-to-Peer Systems, Checkpointing,
Replicated Automata
Mots clefs: Mémoire distribuée virtuellement partagée tolérante aux
fautes, systèmes distribués auto-gérés, systèmes pair-à-pair structurés,
points de reprise, automates dupliqués