skip to main content
10.1145/1316624.1316647acmconferencesArticle/Chapter ViewAbstractPublication PagesgroupConference Proceedingsconference-collections
research-article

Dcv: a causality detection approach for large-scale dynamic collaboration environments

Published: 04 November 2007 Publication History

Abstract

Recent studies have indicated the significance of supporting real-time group editing in "Wiki" applications, whose collaboration environments have their dynamic and large-scale nature. Correct capture of causal relationships between operations from different users is crucial in order to preserve consistency of object copies. This challenge was resolved by employing vector logical clock. But since its size is equal to the number of cooperating sites, it has low efficiency when dealing with a collaborative environment involving a large number of participants. In this paper, we propose a direct causal vector (DCV) approach for solving causality detection issues in real-time group editors. DCV timestamp does not record the causality information that can be deduced from the transitivity of causal relation. As a result, it can automatically reduce its own size when people leave the collaboration session and always keep small. We prove that DCV approach is well fit for capturing causality in wiki like large-scale dynamic collaboration environments.

References

[1]
A. Kittur, B. Suh, B. A. Pendleton, and E. H. Chi. He says, she says: conflict and coordination in wikipedia. In CHI '07: Proceedings of the SIGCHI conference on Human factors in computing systems, pages 453--462, New York, NY, USA, 2007. ACM Press.
[2]
C. A. Ellis and S. J. Gibbs. Concurrency control in groupware systems. In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 399--407, May 1989.
[3]
C. Gutwin and S. Greenberg. The importance of awareness for team cognition in distributed collaboration. Team Cognition: Understanding the Factors that Drive Process and Performance, APA Press, pages 177--201, 2004.
[4]
C. M. Hymes and G. M. Olson. Unblocking brainstorming through the use of a simple group editor. In Proceedings of the ACM Conference on Computer Supported Cooperative Work, pages 99--106, November 1992.
[5]
C. Sun and C. Ellis. Operational transformation in real-time group editors: Issues, algorithms, and achievements. In Proceedings of the ACM Conference on Computer Supported Cooperative Work, pages 59--68, December 1998.
[6]
C. Sun and W. Cai. Capturing causality by compressed vector clock in real-time group editors. International Parallel and Distributed Processing Symposium - Symposium Volume, pages 59--67, 2002.
[7]
C. Sun, X. Jia, Y. Zhang, Y. Yang, and D. Chen. Achieving convergence, causality preservation, and intention preservation in real--time cooperative editing systems. ACM Transactions on Computer-human Interaction, 5(1):63--108, March 1998.
[8]
D. Li and R. Li. Preserving operation effects relation in group editors. In Proceedings of the ACM Conference on Computer Supported Cooperative Work, pages 457--466, November 2004.
[9]
D. Li and R. Li. A landmarkbased transformation approach to concurrency control in group editors. ACM GROUP'05, November 2005.
[10]
D. Li, R. Li, and C. Sun. A time interval based consistency control algorithm for interactive groupware applications. Proceedings of the Parallel and Distributed Systems, pages 429--440, 2004.
[11]
D. Ratner, P. Reiher, and G. Popek. Dynamic version vector maintenance. Technical Report CSD-970022, 1997.
[12]
D. Sun, S. Xia, C. Sun, and D. Chen. Operational transformation for collaborative word processing. Proceedings of the ACM Conference on Computer Supported Cooperative Work CSCW'04, pages 437--446, 2004.
[13]
H. Shen and C. Sun. Flexible notification for collaborative systems. In Proceedings of the ACM Conference on Computer Supported Cooperative Work, pages 77--86, December 2002.
[14]
J. Fowler and W. Zwaenepoel. Causal distributed breakpoints. Proc. of 10th Int. Conference on Distributed Computing Systems, pages 134--141, May 1990.
[15]
L. Lamport. Time, clocks, and the ordering of eevents in a distributed system. Commun. ACM, pages 558--565, 1978.
[16]
M. Singhal and A. Kshemkalyani. An efficient implementation of vector clocks. Information Processing letters, pages 47--52, August 1992.
[17]
M. Suleiman, M. Cart, and J. Ferrie. Serialization of concurrent operations in distributed collaborative environment. ACM GROUP'97, pages 435--445, November 1997.
[18]
N. Gu, J. Yang, and Q. Zhang. Consistency maintenance based on the mark & retrace technique in groupware systems. ACM GROUP'05, pages 264--273, November 2005.
[19]
N. Vidot, M. Cart, J. Ferrie, and M. Suleiman. Copies convergence in a distributed realtime collaborative environment. In Proceedings of the ACM Conference on Computer Supported Cooperative Work, pages 171--180, December 2000.
[20]
R. Schwarz and F. Mattern. Detecting causal relationships in distributed computations: In search of the holy grail. Distributing Computing, pages 149--174, 1994.
[21]
S. Meldal, S. Sankar, and J. Vera. Exploring locality in maintaining potential causality. Proc. of 10th ACM Symposium on Principles of Distributed Computing, pages 231--239, 1991.
[22]
T. Prante and C.Magerkurth. Developping cscw tools for idea finding - empirical results and implications for design. In Proceedings of the ACM Conference on Computer Supported Cooperative Work, pages 106--115, 2002.
[23]
StrategyWiki. http://strategywiki.org/wiki/Main Page.
[24]
WikiNews. http://en.wikinews.org/.
[25]
Wikipedia. What Is Wiki? http://www.wiki.org/wiki.cgi? WhatIsWiki.
[26]
Wikipedia. http://en.wikipedia.org/.
[27]
wikistat. http://www.wikipedia.org/wiki/Wikipedia:Statistics.
[28]
WikiTravel. http://wikitravel.org/en/Main Page.

Cited By

View all
  • (2022)An AST-based consistency maintenance scheme for cross-chain digital assetsCCF Transactions on Pervasive Computing and Interaction10.1007/s42486-022-00096-44:2(142-157)Online publication date: 13-Apr-2022
  • (2022)Self‐compressing object sequence for consistency maintenance in co‐editorsSoftware: Practice and Experience10.1002/spe.309052:8(1802-1825)Online publication date: 21-Apr-2022
  • (2018)A New Algorithm for Real-Time Collaborative Graphical Editing System Based on CRDTComputer Supported Cooperative Work and Social Computing10.1007/978-981-13-3044-5_15(201-212)Online publication date: 11-Dec-2018
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GROUP '07: Proceedings of the 2007 ACM International Conference on Supporting Group Work
November 2007
422 pages
ISBN:9781595938459
DOI:10.1145/1316624
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 November 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. CSCW
  2. concurrency control
  3. direct causal vector
  4. group editors
  5. groupware
  6. logical clock

Qualifiers

  • Research-article

Conference

GROUP07
Sponsor:
GROUP07: ACM 2007 International Conference on Supporting Group Work
November 4 - 7, 2007
Florida, Sanibel Island, USA

Acceptance Rates

Overall Acceptance Rate 125 of 405 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2022)An AST-based consistency maintenance scheme for cross-chain digital assetsCCF Transactions on Pervasive Computing and Interaction10.1007/s42486-022-00096-44:2(142-157)Online publication date: 13-Apr-2022
  • (2022)Self‐compressing object sequence for consistency maintenance in co‐editorsSoftware: Practice and Experience10.1002/spe.309052:8(1802-1825)Online publication date: 21-Apr-2022
  • (2018)A New Algorithm for Real-Time Collaborative Graphical Editing System Based on CRDTComputer Supported Cooperative Work and Social Computing10.1007/978-981-13-3044-5_15(201-212)Online publication date: 11-Dec-2018
  • (2017)ASTS: A string-wise address space transformation algorithm for real-time collaborative editing2017 IEEE 21st International Conference on Computer Supported Cooperative Work in Design (CSCWD)10.1109/CSCWD.2017.8066688(162-167)Online publication date: Apr-2017
  • (2017)A transparent selective undo algorithm for collaborative editing2017 IEEE 21st International Conference on Computer Supported Cooperative Work in Design (CSCWD)10.1109/CSCWD.2017.8066687(156-161)Online publication date: Apr-2017
  • (2017)A string-wise CRDT algorithm for smart and large-scale collaborative editing systemsAdvanced Engineering Informatics10.1016/j.aei.2016.10.00533:C(397-409)Online publication date: 1-Aug-2017
  • (2016)An efficient collaborative editing algorithm supporting string-based operations2016 IEEE 20th International Conference on Computer Supported Cooperative Work in Design (CSCWD)10.1109/CSCWD.2016.7565961(45-50)Online publication date: May-2016
  • (2015)Probabilistic latency for partial ordering2015 International Conference on Protocol Engineering (ICPE) and International Conference on New Technologies of Distributed Systems (NTDS)10.1109/NOTERE.2015.7293483(1-8)Online publication date: Jul-2015

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media