Serveur d'exploration sur la recherche en informatique en Lorraine

Attention, ce site est en cours de développement !
Attention, site généré par des moyens informatiques à partir de corpus bruts.
Les informations ne sont donc pas validées.

Optimistic replication and consitency maintenance in distributed collaborative environments

Identifieur interne : 003990 ( Hal/Curation ); précédent : 003989; suivant : 003991

Optimistic replication and consitency maintenance in distributed collaborative environments

Auteurs : Gérald Oster [France]

Source :

RBID : Hal:tel-00010865

Descripteurs français

English descriptors

Abstract

Collaborative editing systems (CES) allow multiple users to edit the same document. Today, massive collaborative editing becomes reality. CES are not limited to a small amount of users, they are used by thousands users. Unfortunately, current collaborative editing systems were not designed to support such collaboration. Arisen issues are not only technological difficulties; they bring algorithmic foundations of editors into question. The aim of this thesis is to propose new algorithms suitable for massive collaborative editing. We show that theses algorithms must ensure three criterions: copies convergence, intention preservation and scalability. As regards related work, only operational transformation approach (OT) ensures these three criterions.
The first contribution of this dissertation shows that OT approach designed to build real-time collaborative systems can also be used to build asynchronous systems. Using OT, we developed a configuration management tool called SO6. The second contribution is a formal approach to design and verify transformation functions for OT model. This approach relies on an automatic theorem prover. Using this approach, we show that all previously published functions are wrong. The third and last contribution of this research is a new optimistic algorithm (WOOT) that is suitable for massive collaborative editing of linear structures. This algorithm relies on a monotonic computation of a linear extension of partial orders built from relations between elements of the structure.

Url:

Links toward previous steps (curation, corpus...)


Links to Exploration step

Hal:tel-00010865

Le document en format XML

<record>
<TEI>
<teiHeader>
<fileDesc>
<titleStmt>
<title xml:lang="en">Optimistic replication and consitency maintenance in distributed collaborative environments</title>
<title xml:lang="fr">Réplication optimiste et cohérence des données dans les environnements collaboratifs répartis</title>
<author>
<name sortKey="Oster, Gerald" sort="Oster, Gerald" uniqKey="Oster G" first="Gérald" last="Oster">Gérald Oster</name>
<affiliation wicri:level="1">
<hal:affiliation type="researchteam" xml:id="struct-2349" status="OLD">
<idno type="RNSR">199918294U</idno>
<orgName>Environment for cooperation</orgName>
<orgName type="acronym">ECOO</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/ecoo</ref>
</desc>
<listRelation>
<relation active="#struct-160" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-300291" type="indirect"></relation>
<relation active="#struct-300292" type="indirect"></relation>
<relation active="#struct-300293" type="indirect"></relation>
<relation active="#struct-2496" type="direct"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-160" type="direct">
<org type="laboratory" xml:id="struct-160" status="OLD">
<orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<desc>
<address>
<addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation>
<relation name="UMR7503" active="#struct-441569" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-300291" type="direct"></relation>
<relation active="#struct-300292" type="direct"></relation>
<relation active="#struct-300293" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect">
<org type="institution" xml:id="struct-441569" status="VALID">
<idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc>
<address>
<country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect">
<org type="institution" xml:id="struct-300009" status="VALID">
<orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc>
<address>
<addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300291" type="indirect">
<org type="institution" xml:id="struct-300291" status="OLD">
<orgName>Université Henri Poincaré - Nancy 1</orgName>
<orgName type="acronym">UHP</orgName>
<date type="end">2011-12-31</date>
<desc>
<address>
<addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300292" type="indirect">
<org type="institution" xml:id="struct-300292" status="OLD">
<orgName>Université Nancy 2</orgName>
<date type="end">2011-12-31</date>
<desc>
<address>
<addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300293" type="indirect">
<org type="institution" xml:id="struct-300293" status="OLD">
<orgName>Institut National Polytechnique de Lorraine</orgName>
<orgName type="acronym">INPL</orgName>
<date type="end">2011-12-31</date>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-2496" type="direct">
<org type="laboratory" xml:id="struct-2496" status="OLD">
<orgName>INRIA Lorraine</orgName>
<desc>
<address>
<addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref>
</desc>
<listRelation>
<relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName>
<settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université Nancy 2</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
<placeName>
<settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Institut national polytechnique de Lorraine</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:tel-00010865</idno>
<idno type="halId">tel-00010865</idno>
<idno type="halUri">https://tel.archives-ouvertes.fr/tel-00010865</idno>
<idno type="url">https://tel.archives-ouvertes.fr/tel-00010865</idno>
<date when="2005-11-03">2005-11-03</date>
<idno type="wicri:Area/Hal/Corpus">003990</idno>
<idno type="wicri:Area/Hal/Curation">003990</idno>
</publicationStmt>
<sourceDesc>
<biblStruct>
<analytic>
<title xml:lang="en">Optimistic replication and consitency maintenance in distributed collaborative environments</title>
<title xml:lang="fr">Réplication optimiste et cohérence des données dans les environnements collaboratifs répartis</title>
<author>
<name sortKey="Oster, Gerald" sort="Oster, Gerald" uniqKey="Oster G" first="Gérald" last="Oster">Gérald Oster</name>
<affiliation wicri:level="1">
<hal:affiliation type="researchteam" xml:id="struct-2349" status="OLD">
<idno type="RNSR">199918294U</idno>
<orgName>Environment for cooperation</orgName>
<orgName type="acronym">ECOO</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/ecoo</ref>
</desc>
<listRelation>
<relation active="#struct-160" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-300291" type="indirect"></relation>
<relation active="#struct-300292" type="indirect"></relation>
<relation active="#struct-300293" type="indirect"></relation>
<relation active="#struct-2496" type="direct"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-160" type="direct">
<org type="laboratory" xml:id="struct-160" status="OLD">
<orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<desc>
<address>
<addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation>
<relation name="UMR7503" active="#struct-441569" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-300291" type="direct"></relation>
<relation active="#struct-300292" type="direct"></relation>
<relation active="#struct-300293" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect">
<org type="institution" xml:id="struct-441569" status="VALID">
<idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc>
<address>
<country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect">
<org type="institution" xml:id="struct-300009" status="VALID">
<orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc>
<address>
<addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300291" type="indirect">
<org type="institution" xml:id="struct-300291" status="OLD">
<orgName>Université Henri Poincaré - Nancy 1</orgName>
<orgName type="acronym">UHP</orgName>
<date type="end">2011-12-31</date>
<desc>
<address>
<addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300292" type="indirect">
<org type="institution" xml:id="struct-300292" status="OLD">
<orgName>Université Nancy 2</orgName>
<date type="end">2011-12-31</date>
<desc>
<address>
<addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300293" type="indirect">
<org type="institution" xml:id="struct-300293" status="OLD">
<orgName>Institut National Polytechnique de Lorraine</orgName>
<orgName type="acronym">INPL</orgName>
<date type="end">2011-12-31</date>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-2496" type="direct">
<org type="laboratory" xml:id="struct-2496" status="OLD">
<orgName>INRIA Lorraine</orgName>
<desc>
<address>
<addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref>
</desc>
<listRelation>
<relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName>
<settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université Nancy 2</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
<placeName>
<settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Institut national polytechnique de Lorraine</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc>
<textClass>
<keywords scheme="mix" xml:lang="en">
<term>Collaborative systems</term>
<term>data consistency</term>
<term>formal verification</term>
<term>operational transformation</term>
<term>optimistic replication</term>
</keywords>
<keywords scheme="mix" xml:lang="fr">
<term>Systèmes collaboratifs</term>
<term>cohérence des données</term>
<term>réconciliation</term>
<term>réplication optimiste</term>
<term>transformées opérationnelles</term>
<term>vérification formelle</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front>
<div type="abstract" xml:lang="en">Collaborative editing systems (CES) allow multiple users to edit the same document. Today, massive collaborative editing becomes reality. CES are not limited to a small amount of users, they are used by thousands users. Unfortunately, current collaborative editing systems were not designed to support such collaboration. Arisen issues are not only technological difficulties; they bring algorithmic foundations of editors into question. The aim of this thesis is to propose new algorithms suitable for massive collaborative editing. We show that theses algorithms must ensure three criterions: copies convergence, intention preservation and scalability. As regards related work, only operational transformation approach (OT) ensures these three criterions.
The first contribution of this dissertation shows that OT approach designed to build real-time collaborative systems can also be used to build asynchronous systems. Using OT, we developed a configuration management tool called SO6. The second contribution is a formal approach to design and verify transformation functions for OT model. This approach relies on an automatic theorem prover. Using this approach, we show that all previously published functions are wrong. The third and last contribution of this research is a new optimistic algorithm (WOOT) that is suitable for massive collaborative editing of linear structures. This algorithm relies on a monotonic computation of a linear extension of partial orders built from relations between elements of the structure.</div>
</front>
</TEI>
<hal api="V3">
<titleStmt>
<title xml:lang="en">Optimistic replication and consitency maintenance in distributed collaborative environments</title>
<title xml:lang="fr">Réplication optimiste et cohérence des données dans les environnements collaboratifs répartis</title>
<author role="aut">
<persName>
<forename type="first">Gérald</forename>
<surname>Oster</surname>
</persName>
<email>oster@loria.fr</email>
<idno type="idhal">gerald-oster</idno>
<idno type="halauthor">62753</idno>
<affiliation ref="#struct-2349"></affiliation>
</author>
<editor role="depositor">
<persName>
<forename>Gérald</forename>
<surname>Oster</surname>
</persName>
<email>gerald.oster@loria.fr</email>
</editor>
</titleStmt>
<editionStmt>
<edition n="v1" type="current">
<date type="whenSubmitted">2005-11-04 15:52:22</date>
<date type="whenModified">2016-05-19 01:09:21</date>
<date type="whenReleased">2005-11-04 16:40:13</date>
<date type="whenProduced">2005-11-03</date>
<date type="whenEndEmbargoed">2005-11-04</date>
<ref type="file" target="https://tel.archives-ouvertes.fr/tel-00010865/document">
<date notBefore="2005-11-04"></date>
</ref>
<ref type="file" n="1" target="https://tel.archives-ouvertes.fr/tel-00010865/file/tel-00010865.pdf">
<date notBefore="2005-11-04"></date>
</ref>
</edition>
<respStmt>
<resp>contributor</resp>
<name key="107193">
<persName>
<forename>Gérald</forename>
<surname>Oster</surname>
</persName>
<email>gerald.oster@loria.fr</email>
</name>
</respStmt>
</editionStmt>
<publicationStmt>
<distributor>CCSD</distributor>
<idno type="halId">tel-00010865</idno>
<idno type="halUri">https://tel.archives-ouvertes.fr/tel-00010865</idno>
<idno type="halBibtex">oster:tel-00010865</idno>
<idno type="halRefHtml">Autre [cs.OH]. Université Henri Poincaré - Nancy I, 2005. Français</idno>
<idno type="halRef">Autre [cs.OH]. Université Henri Poincaré - Nancy I, 2005. Français</idno>
</publicationStmt>
<seriesStmt>
<idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
<idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
<idno type="stamp" n="INPL">Institut National Polytechnique de Lorraine</idno>
<idno type="stamp" n="LORIA2">Publications du LORIA</idno>
<idno type="stamp" n="INRIA-NANCY-GRAND-EST">INRIA Nancy - Grand Est</idno>
<idno type="stamp" n="LORIA-NSS" p="LORIA">Réseaux, systèmes et services</idno>
<idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno>
<idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno>
<idno type="stamp" n="INRIA-LORRAINE">INRIA Nancy - Grand Est</idno>
<idno type="stamp" n="LABO-LORIA-SET" p="LORIA">LABO-LORIA-SET</idno>
</seriesStmt>
<notesStmt></notesStmt>
<sourceDesc>
<biblStruct>
<analytic>
<title xml:lang="en">Optimistic replication and consitency maintenance in distributed collaborative environments</title>
<title xml:lang="fr">Réplication optimiste et cohérence des données dans les environnements collaboratifs répartis</title>
<author role="aut">
<persName>
<forename type="first">Gérald</forename>
<surname>Oster</surname>
</persName>
<email>oster@loria.fr</email>
<idno type="idHal">gerald-oster</idno>
<idno type="halAuthorId">62753</idno>
<affiliation ref="#struct-2349"></affiliation>
</author>
</analytic>
<monogr>
<imprint>
<date type="dateDefended">2005-11-03</date>
</imprint>
<authority type="institution">Université Henri Poincaré - Nancy I</authority>
<authority type="supervisor">Godart Claude(claude.godart@loria.fr)</authority>
<authority type="jury">Molli Pascal (co-directeur)</authority>
<authority type="jury">Jean Ferrié (rapporteur)</authority>
<authority type="jury">Marc Shapiro (rapporteur)</authority>
<authority type="jury">Jens Gustedt (président)</authority>
<authority type="jury">Michel Raynal (membre invité)</authority>
</monogr>
</biblStruct>
</sourceDesc>
<profileDesc>
<langUsage>
<language ident="fr">French</language>
</langUsage>
<textClass>
<keywords scheme="author">
<term xml:lang="en">Collaborative systems</term>
<term xml:lang="en">optimistic replication</term>
<term xml:lang="en">data consistency</term>
<term xml:lang="en">operational transformation</term>
<term xml:lang="en">formal verification</term>
<term xml:lang="fr">Systèmes collaboratifs</term>
<term xml:lang="fr">réplication optimiste</term>
<term xml:lang="fr">cohérence des données</term>
<term xml:lang="fr">transformées opérationnelles</term>
<term xml:lang="fr">réconciliation</term>
<term xml:lang="fr">vérification formelle</term>
</keywords>
<classCode scheme="halDomain" n="info.info-oh">Computer Science [cs]/Other [cs.OH]</classCode>
<classCode scheme="halTypology" n="THESE">Theses</classCode>
</textClass>
<abstract xml:lang="en">Collaborative editing systems (CES) allow multiple users to edit the same document. Today, massive collaborative editing becomes reality. CES are not limited to a small amount of users, they are used by thousands users. Unfortunately, current collaborative editing systems were not designed to support such collaboration. Arisen issues are not only technological difficulties; they bring algorithmic foundations of editors into question. The aim of this thesis is to propose new algorithms suitable for massive collaborative editing. We show that theses algorithms must ensure three criterions: copies convergence, intention preservation and scalability. As regards related work, only operational transformation approach (OT) ensures these three criterions.
The first contribution of this dissertation shows that OT approach designed to build real-time collaborative systems can also be used to build asynchronous systems. Using OT, we developed a configuration management tool called SO6. The second contribution is a formal approach to design and verify transformation functions for OT model. This approach relies on an automatic theorem prover. Using this approach, we show that all previously published functions are wrong. The third and last contribution of this research is a new optimistic algorithm (WOOT) that is suitable for massive collaborative editing of linear structures. This algorithm relies on a monotonic computation of a linear extension of partial orders built from relations between elements of the structure.</abstract>
<abstract xml:lang="fr">Les systèmes d'édition collaborative permettent à plusieurs utilisateurs d'éditer simultanément un document. Aujourd'hui, l'édition collaborative massive est une réalité. Il ne s'agit plus d'éditer à quelques utilisateurs mais à des milliers d'utilisateurs répartis dans le monde. Les éditeurs collaboratifs actuels n'ont pas été conçus pour supporter un nombre si important d'utilisateurs. Les problèmes soulevés ne sont pas d'ordre technologique, ils remettent en cause les fondements algorithmiques des éditeurs. L'objectif de cette thèse est de proposer des algorithmes adaptés à l'édition collaborative massive. Nous montrons qu'un tel algorithme doit assurer trois critères : convergence des données, préservation des intentions et passage à l'échelle. Au regard de l'état de l'art, seul le modèle des transformées opérationnelles (OT) peut concilier ces trois critères.
La première contribution de cette thèse montre que l'approche OT conçue pour des éditeurs temps réel peut être utilisée pour réaliser des outils asynchrones. Nous avons réalisé un gestionnaire de configurations dénommé SO6. La seconde contribution est une approche formelle à la conception et à la vérification de fonctions de transformation pour le modèle OT. Cette approche repose sur un démonstrateur automatique de théorème. Avec cette approche, nous montrons que toutes les fonctions de transformation proposées jusqu'ici sont fausses. La troisième et dernière contribution de ce travail est un nouvel algorithme de réplication optimiste (WOOT) adapté à l'édition collaborative massive de structures linéaires. Ce modèle repose sur le calcul monotone d'une extension linéaire des ordres partiels formés par les relations entre les différents éléments de la structure.</abstract>
</profileDesc>
</hal>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003990 | SxmlIndent | more

Ou

HfdSelect -h $EXPLOR_AREA/Data/Hal/Curation/biblio.hfd -nk 003990 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Hal
   |étape=   Curation
   |type=    RBID
   |clé=     Hal:tel-00010865
   |texte=   Optimistic replication and consitency maintenance in distributed collaborative environments
}}

Wicri

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022