Nicolas Vidot
ABSTRACT
In real-time collaborative systems, replicated objects, shared by users, are subject to concurrency constraints. In order to satisfy these, various algorithms, qualified as op?timistic, [3, 5, 13, 17, 14, 15, 18], have been proposed that exploit the semantic properties of operations to serialize concurrent operations and achieve copy con?vergence of replicated objects. Their drawback is that they either re?quire a condition on user's operations which is hard to verify when possible to ensure, or they need undo?ing then redoing operations in some situations. The main purpose of this paper is to present two new algorithms that over?come these drawbacks. They are based upon the imple?mentation of a continuous global order which enables that condition to be released, and simplifies the operation inte?gration process. In the second algorithm, thanks to de?ferred broadcast of operations to other sites, this process becomes even more simplified.
- 1.Allison C.: Concurrency Control for Real Time Groupware, CE94: Concurrent Engineering Research and Applications. A global Perspective, Pittsbourg, August 1994, pp. 163-170.Google Scholar
- 2.Banino J.S., Kaiser C., Zimmermann H.: Synchronization for distributed systems using a single broadcast channel,Proc. 1 st Int. Conf. on Distributed Computing Systems, Huntsville, October 1979.Google Scholar
- 3.Ellis C.A., Gibbs S.J.: Concurency Control in Groupware Systems; Proc. ACM Int. Conf. on Management of Data (SIGMOD'89), Seattle, May 1989, pp. 399-407. Google ScholarDigital Library
- 4.Ellis C.A., Gibbs S.J., Rein G.L.: Groupware : Some issues and experiences; Commun. ACM, January 1991, vol.34, n~ 1, pp. 39-59. Google ScholarDigital Library
- 5.Karsenty A., Beaudouin-Lafon M.: An Algorithm for Distributed Groupware Applications;Proc.13 th Int. Conf. on Distributed Computing Systems (ICDCS'93), Pittsburgh, May 1993, pp. 195-202.Google Scholar
- 6.Lamport L.: Time, Clocks, and the Ordering of Events in Distributed System; Commun. ACM, July 1978, vol. 21, n~ 7, pp. 558-565. Google ScholarDigital Library
- 7.Le Lann G.: Algorithms for distributed data sharing systems which use tickets;Proc.3 rd Workshop on Distributed Data Management and Computer Networks, Berkeley, August 1978.Google Scholar
- 8.Mattern F.: Virtual time and global states of Distributed Systems; Proc. Int. Workshop on Parallel and Distributed Algorithms, Elsevier Pub., 1989, pp. 215-276.Google Scholar
- 9.Nichols D., Curtis P., Dixon M., J. Lamping: High-latency, low-bandwidth windowing in the Jupiter collaboration system; Proc. ACM Symposium on User Interface Sofware and Technologies, November 1995, pp. 111-120. Google ScholarDigital Library
- 10.Palmer C.R., Cormack G.V.: Operation Transforms for a Distributed Shared Spreadsheet; Proc. ACM Int. Conf. on Computer Supported Cooperative Work (CSCW'98), Seattle, November 1998, pp. 69-78. Google ScholarDigital Library
- 11.Prakash A., Knister M.J.: Undoing Actions in Collaborative Work; Proc. ACM Int. Conf. on Computer Supported Cooperative Work (CSCW'92), November 1992, pp. 273-280. Google ScholarDigital Library
- 12.Reed D.P., Kanodia R.K.: Synchronisation with eventcounts and sequencers; Commun. ACM, February 1979, vol. 22, n~ 2, pp. 115-123. Google ScholarDigital Library
- 13.Ressel M., Nitsche-Ruhland D., Gunzenh~user R.: An Integrating, Transformation-oriented Approach to Concurrency Control and Undo in Group Editors; Proc. ACM Int. Conf. on Computer Supported Cooperative Work (CSCW'96), Boston, November 1996, pp. 288-297. Google ScholarDigital Library
- 14.Suleiman M., Cart M., Ferri~ J.: Serialization of Concurrent Operations in Distributed Collaborative Environment ;Proc. ACM Int. Conf. on Supporting Group Work (GROUP'97), Phoenix, November 1997, pp. 435-445. Google ScholarDigital Library
- 15.Suleiman M., Cart M., Ferri~ J.: Concurrent Operations in a Distributed and Mobile Collaborative Environment ;Proc. 14 th IEEE Int. Conf. on Data Engineering (IEEE / ICDE'98), Orlando, February 1998, pp. 36-45. Google ScholarDigital Library
- 16.Suleiman M.: S~rialisation des op~rations concurrentes dans les syst~mes collaboratifs r~partis ; PhD thesis, University of Montpellier 2, July 1998.Google Scholar
- 17.Sun C., Jia X., Yang Y., Zhang Y.: A generic operation transformation schema for consistency maintenance in realtime cooperative editing systems; Proc. ACM Int. Conf. on Supporting Group Work (GROUP'97), Phoenix, November 1997, pp. 425-434. Google ScholarDigital Library
- 18.Sun C., Ellis C.S.: Operational Transformation in Real- Time Group Editors : Issues, Algorithms and Achievements ; Proc. ACM Int. Conf. on Computer Supported Cooperative Work (CSCW'98), Seattle, November 1998, pp. 59-68. Google ScholarDigital Library
- 19.Weihl W.E.: Commutativity-Based Concurrency Control for Abstract Data Type; IEEE Transactions On Computers, vol. 37, n~ 12, December 1988, pp. 1488-1505. Google ScholarDigital Library
Index Terms
- Copies convergence in a distributed real-time collaborative environment
Recommendations
Enhancing availability in distributed real-time databases
Special Issue on Real-Time Database SystemsOne of the issues in distributed databases is to maintain the data consistency when a database is replicated for higher availability. In a real-time database system, availability may be more important than consistency since a result must be produced ...
Regeneration with Virtual Copies for Distributed Computing Systems
The authors consider the consistency control problem for replicated data in a distributed computing system (DCS) and propose a new algorithm to dynamically regenerate copies of data objects in response to node failures and network partitioning in the ...
Comments