Département d'informatique, Institut d'informatique fondamentale IIF (Laboratoire de systèmes répartis LSR)

Concepts et mécanismes pour la mise en oeuvre d'un environnement d'édition coopérative sur un réseau à grande échelle

Pacull, François ; Schiper, André (Dir.)

Thèse Ecole polytechnique fédérale de Lausanne EPFL : 1995 ; no 1335.

Ajouter à la liste personnelle
    Summary
    The following dissertation addresses one aspect of cooperative editing which has not been well examined until now : the consideration of hardware limitations imposed by a large scale distributed system (namely the Internet). This system model implies heterogeneous hardware, unbounded communication delays, and process failures. In this context, mechanisms usually used for cooperative editing in a local area network are not suitable. The model proposed here is based on a dynamic decomposition of the document into independant parts, maintained by a replicated kernel. The decomposition is controlled by the users themselves, who can then act on the concurrency allowed at the document level. The more a document is fragmented, the more concurrency is allowed. The replication of the independant document parts within the kernel, ensures the document availability and this regardless of the performances of the users' sites. Communication is reduced to minimum, thus allowing use in large scale distributed system. Users interact with the kernel either by copying a kernel object to their own local environment where it can be modified, or by handling over the modified object to the kernel. Consistency is managed according to several policies that can be chosen by the user depending on the document maturity or the required interaction with the other users. A new criterion has been defined to ensure consistency : the NRT-linearizability. This criterion is more adapted to our problem than linearizability, and allows in particular a non-blocking implementation even in the case of failures (user site as well as kernel site failure), which is important when considering large scale distributed system. This criterion maintains the locality property of the linearizability. Contrary to the classical approach, this criterion is not applied to the read-modify-write operations ensuring the atomicity of the following actions : loading a document part into an editor, modifying it with the editor, and storing the modified part. The atomicity of the read-modify-write operations is only considered ot the application level and takes into account the knowledge of the users. Thus, the user is free to choose the way it will be performed His her choice will be made between several concurrency control policies based on rules established between the users, either optimistic based on conflict detection, pessimistic based on capabilities, or hybrid.
    Résumé
    Dans ce travail de thèse nous abordons un aspect de l'édition coopérative peu exploré jusqu'à présent : la considération des limitations imposées par un réseau à grande échelle (typiquement Internet). Ce modèle de système implique l'hétérogénéité des machines, des délais de communication non bornés et des pannes. Dans ce contexte, les techniques traditionnelles utilisées pour l'édition coopérative dans un réseau local sont inadaptées. Le modèle proposé dans cette thèse est basé sur une décomposition dynamique du document en parties indépendantes, maintenues individuellement par un noyau dupliqué. La décomposition est contrôlée par les utilisateurs eux-mêmes, qui peuvent ainsi agir sur la concurrence autorisée au niveau du document. Plus un document est fragmenté, plus la concurrence potentielle est grande. La duplication des parties indépendantes au sein d'un noyau partagé permet d'assurer la disponibilité du document aux utilisateurs, et ce indépendamment des performances des sites utilisateurs. Les communications sont réduites au minimum, autorisant une utilisation à large échelle. Les utilisateurs interagissent avec le noyau soit en récupérant une copie locale d'un objet du noyau qu'ils peuvent modifier à loisir dans leur environnement local, soit au contraire en transmettant au niveau du noyau une copie locale. La gestion de la cohérence se faisant à ce moment là suivant plusieurs politiques que l'utilisateur peut choisir en fonction de la maturité du document ou encore des autres utilisateurs. Concernant la gestion de la cohérence, un critère à été défini : la NTR-linéarisabilité. C'est un critère mieux adapté que la linéarisabilité, qui permet en particulier une mise en oeuvre non bloquante en cas de panne (panne d'un site utilisateur ou panne d'un site du noyau), ce qui est important dans le cadre des réseaux à large échelle. Ce critère conserve la propriété de localité de la linéarisabilité. Contrairement à l'approche classique, ce critère de cohérence n'est pas appliqué aux opérations lecture-modification-écriture garantissant l'atomicité des actions suivantes : chargement dans un fichier d'une partie de document, modification grâce à l'éditeur, puis finalement sauvegarde de la partie ainsi modifiée. La mise en oeuvre assure uniquement l'atomicité des opérations d'écriture et de lecture. L'atomicité des opérations lecture-modification-écriture est considérée uniquement au niveau applicatif, afin de prendre en considération les connaissances des utilisateurs. Ainsi, la manière dont elle va être réalisée est laissée au choix des utilisateurs, grâce à plusieurs politiques de contrôle de concurrence qui dépendront de règles établies entre les utilisateurs, soit optimistes basées sur des détections de conflit a posteriori, soit pessimistes basées sur des capacités, soit hybrides.