Browse wiki

Jump to: navigation, search
Logoot-undo: distributed collaborative editing system on P2P networks
Abstract Peer-to-peer systems provide scalable contPeer-to-peer systems provide scalable content distribution for cheap and resist to censorship attempts. However, P2P networks mainly distribute immutable content and provide poor support for highly dynamic content such as produced by collaborative systems. A new class of algorithms called CRDT (Commutative} Replicated Data Type), which ensures consistency of highly dynamic content on P2P networks, is emerging. However, if existing CRDT algorithms support the edit anywhere anytime feature they do not support the "undo anywhere anytime feature. In this paper we present the Logoot-Undo CRDT algorithm which integrates the "undo anywhere anytime feature. We compare the performance of the proposed algorithm with related algorithms and measure the impact of the undo feature on the global performance of the algorithm. We prove that the cost of the undo feature remains low on a corpus of data extracted from Wikipedia.a corpus of data extracted from Wikipedia.
Added by wikilit team Added on initial load  +
Collected data time dimension Longitudinal  +
Conclusion . As expected, the undo feature increases . As expected, the undo feature increases the overhead for Logoot-Undo. On the contrary, since the undo mechanisms of WOOT and MOT2 reuse tombstones, their overheads decrease while including undo modifications. . Tombstone-based approaches eventually degrade in performance over time. Indeed, the number of edits on a document can only grow. . The Boundary Strategy of Logoot-Undo has an overhead slightly bigger than the Random Strategy on most edited articles and on longest articles. Otherwise, on the most edited pages, the Boundary Strategy improves greatly Logoot-Undo overhead. Finally, in average, the Boundary Strategy offers the lowest overhead. . Logoot-Undo with Boundary Strategy is the only approach that has for every category an overhead less than half of the document size. These experiments show that, even in case of undo, Logoot-Undo is more scalable than existing approaches. . Thanks to its very small tombstones (one character per deleted line) and its absence of line identifier, MOT2 overhead is quite small in the average case. Unfortunately, its algorithmic complexity, which is proportional to the number of tombstones, will monotonically grow. Also, MOT2 dissemination uses a pairwise reconciliation mechanism that exchanges messages whose size is proportional to the number of operations ever received on a peer. On the contrary, WOOT and Logoot dissemination mechanisms send only constant-size messages.chanisms send only constant-size messages.
Data source Experiment responses  + , Wikipedia pages  +
Doi 10.1109/TPDS.2009.173 +
Google scholar url http://scholar.google.com/scholar?ie=UTF-8&q=%22Logoot-undo%3A%2Bdistributed%2Bcollaborative%2Bediting%2Bsystem%2Bon%2BP2P%2Bnetworks%22  +
Has author Stephane Weiss + , Pascal Urso + , Pascal Molli +
Has domain Computer science +
Has topic Other corpus topics +
Issue 8  +
Pages 1162-1174  +
Peer reviewed Yes  +
Publication type Journal article  +
Published in IEEE Transactions on Parallel and Distributed Systems +
Research design Experiment  +
Research questions In this paper, we present the Logoot-Undo In this paper, we present the Logoot-Undo CRDT algorithm that integrates the “undo anywhere, anytime” feature. We compare the performance of the proposed algorithm with related algorithms and measure the impact of the undo feature on the global performance of the algorithm. We prove that the cost of the undo feature remains low on a corpus of data extracted from Wikipedia.a corpus of data extracted from Wikipedia.
Revid 10,862  +
Theories Undetermined
Theory type Design and action  +
Title Logoot-undo: distributed collaborative editing system on P2P networks
Unit of analysis Edit  +
Url http://dx.doi.org/10.1109/TPDS.2009.173  +
Volume 21  +
Wikipedia coverage Sample data  +
Wikipedia data extraction Live Wikipedia  +
Wikipedia language English  +
Wikipedia page type Article  +
Year 2010  +
Creation dateThis property is a special property in this wiki. 15 March 2012 20:29:33  +
Categories Other corpus topics  + , Computer science  + , Publications with missing comments  + , Publications  +
Modification dateThis property is a special property in this wiki. 30 January 2014 20:29:33  +
hide properties that link here 
  No properties link to this page.
 

 

Enter the name of the page to start browsing from.