Article

The IceCube approach to the reconciliation of divergent replicas

Authors:

Anne-Marie Kermarrec,

Antony Rowstron,

Marc Shapiro,

Peter DruschelAuthors Info & Claims

PODC '01: Proceedings of the twentieth annual ACM symposium on Principles of distributed computing

Pages 210 - 218

https://doi.org/10.1145/383962.384020

Published: 01 August 2001 Publication History

Get Access

Abstract

We describe a novel approach to log-based reconciliation called IceCube. It is general and is parameterised by application and object semantics. IceCube considers more flexible orderings and is designed to ease the burden of reconciliation on the application programmers. IceCube captures the static and dynamic reconciliation constraints between all pairs of actions, proposes schedules that satisfy the static constraints, and validates them against the dynamic constraints.

Preliminary experience indicates that strong static constraints successfully contain the potential combinatorial explosion of the simulation stage. With weaker static constraints, the system still finds good solutions in a reasonable time.

References

[1]

S. Balasubramaniam and B. C. Pierce. What is a file synchronizer? In Int. Conf. on Mobile Comp. and Netw. (MobiCom '98). ACM/IEEE, Oct. 1998. http:// www.cis.upenn.edu/~bcpierce/papers/snc- mobicom.ps.

Digital Library

Google Scholar

[2]

M. Berger, A. Schill, and G. Volksen. Supporting autonomous work and reintegration in collaborative systems. In W. Conen and G. Neumann, editors, Coordination Technology for Collaborative Applications -- Organizations, Processes, and Agents, pages 177-198, New York, 1998. Springer. http:// wwwrn.inf.tu-dresclen.de/Isrn/Ps-Files/autonomous.ps.

Digital Library

Google Scholar

[3]

P. Cederqvist et al. Version management with CVS, 1992.

Google Scholar

[4]

O. Dedieu. RdpHcation optimiste pour les applications collaboratives asynchrones. Phi) thesis, Universitd de Marne-la-Vallde, Marne-la-Vallde (France), Sept. 2000. http://www-sor.inria.fr/~dedieu/these.html.

Google Scholar

[5]

W. K. Edwards, E. D. Mynatt, K. Pertersen, M. J. Spreitzer, D. B. Terry, and M. M. Theimer. Designing and implementing asynchonons applications with Bayou. In Syrup. on User Int. Software and Tech., Banff Alberta (Canada), Oct. 1997.

Digital Library

Google Scholar

[6]

F. Fages. A constraint programming approach to log-based reconciliation problems for nomadic applications. In 6th Annual W. of the ERCIM Working Group on Constraints, Prague (Czech Republic), June 2001.

Google Scholar

[7]

M. Herfihy. Apologizing versus asking permission: optimistic concurrency control for abstract data types. Commun. A CM, 15(1):96-124, 1990.

Digital Library

Google Scholar

[8]

P. Kumar and M. Satyanarayanan. Flexible and safe resolution of file conflicts. In Proe. of the Useniz Winter 1995, Jan. 1995.

Digital Library

Google Scholar

[9]

H. T. Kung and J. T. Robinson. On optimistic methods for concurrency control. A CM Trans. Database Syst., 6(2), June 1981.

Digital Library

Google Scholar

[10]

K. Petersen, M. J. Spreitzer, D. B. Terry, M. M. Theimer, and A. J. Demers. Flexible update propagation for weakly consistent replication. In Proc. Syrup. on Operating Systems Principles (SOSP-16), pages 288-301, Saint Malo, OCt. 1997. ACM SIGOPS. http: / /www.parc.xerox.com/csl/projects/bayou/.

Digital Library

Google Scholar

[11]

S. H. Phatak and B. R. Badrinath. and Conflict resolution reconcilation in disconnected databases. In 2nd Int. W. Mobility in Databases and Dist. Sys. (MDDS'99), Florence (Italy), Aug.-Sept. 1999. http: //www.cs.rutgers.edu/~badri/papers/reconciliation.pdf

Google Scholar

[12]

N. Ramsey and E. Csirmaz. An algebraic approach to file synchronization. Technical Report TR-05-01, Harvard University Dept. of Computer Science, Cambridge MA (USA), May 2001.

Digital Library

Google Scholar

[13]

P. M. Schwartz and A. Z. Spector. Synchronizing shared abstract types. A CM Trans. Comput. Syst. 2(3):223-250, Aug. 1984.

Digital Library

Google Scholar

[14]

C. Sun and C. Ellis. Operational transformation in real-time group editors: issues, algorithms, and achievements. In Conf. on Comp.-Supported Cooperative Work (CSCW), page 59, Seattle WA (USA), Nov. 1998. http://www.acm.org/pubs/articles/ proceedings/cscw/289444/p59-sun/p59-su% n. pdf.

Digital Library

Google Scholar

Cited By

View all

Csirmaz ECsirmaz L(2022)Data Synchronization: A Complete Theoretical Solution for FilesystemsFuture Internet10.3390/fi1411034414:11(344)Online publication date: 21-Nov-2022
https://doi.org/10.3390/fi14110344
Csirmaz ECsirmaz L(2022)Algebra of Data ReconciliationStudia Scientiarum Mathematicarum Hungarica10.1556/012.2022.0152959:3-4(209-231)Online publication date: 14-Dec-2022
https://doi.org/10.1556/012.2022.01529
Schiefer NLitt GJackson DSzekeres ASivaramakrishnan K(2022)Merge what you can, fork what you can'tProceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data10.1145/3517209.3524041(24-32)Online publication date: 5-Apr-2022
https://dl.acm.org/doi/10.1145/3517209.3524041
Show More Cited By

Index Terms

The IceCube approach to the reconciliation of divergent replicas
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
2. Theory of computation
  1. Models of computation
    1. Probabilistic computation
  2. Semantics and reasoning
    1. Program semantics
      1. Denotational semantics

Recommendations

Feasibility of online divergent thinking assessment

The project examined creative thinking in online settings.The goal was to aid creative thinking research by increasing ecological validity.Online administration had no detrimental affect on divergent thinking.Imposition of time limits effectively ...
The effect of group composition on divergent thinking in an interaction design activity
DIS '06: Proceedings of the 6th conference on Designing Interactive systems

Nearly 50 years of empirical research has suggested that social influences have an inhibiting effect on creativity in collaborating groups such as design teams. This suggests that design teams may not be as creative as they could be, resulting in a ...
The Effects of Generative AI on Design Fixation and Divergent Thinking
CHI '24: Proceedings of the 2024 CHI Conference on Human Factors in Computing Systems

Generative AI systems have been heralded as tools for augmenting human creativity and inspiring divergent thinking, though with little empirical evidence for these claims. This paper explores the effects of exposure to AI-generated images on measures of ...

Comments

Information & Contributors

Information

Published In

PODC '01: Proceedings of the twentieth annual ACM symposium on Principles of distributed computing

August 2001

323 pages

ISBN:1581133839

DOI:10.1145/383962

Chairmen:
Ajay Kshemkalyani
Univ. of Illinois at Chicago, Chicago
,
Nir Shavit
Tel-Aviv Univ.; and Sun Labs.

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODC01

Sponsor:

PODC01: 20th Annual ACM Symposium on Principles of Distributed Computing

Rhode Island, Newport, USA

Acceptance Rates

PODC '01 Paper Acceptance Rate 39 of 118 submissions, 33%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

101
Total Citations
View Citations
680
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Csirmaz ECsirmaz L(2022)Data Synchronization: A Complete Theoretical Solution for FilesystemsFuture Internet10.3390/fi1411034414:11(344)Online publication date: 21-Nov-2022
https://doi.org/10.3390/fi14110344
Csirmaz ECsirmaz L(2022)Algebra of Data ReconciliationStudia Scientiarum Mathematicarum Hungarica10.1556/012.2022.0152959:3-4(209-231)Online publication date: 14-Dec-2022
https://doi.org/10.1556/012.2022.01529
Schiefer NLitt GJackson DSzekeres ASivaramakrishnan K(2022)Merge what you can, fork what you can'tProceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data10.1145/3517209.3524041(24-32)Online publication date: 5-Apr-2022
https://dl.acm.org/doi/10.1145/3517209.3524041
De Porre KFerreira CPreguiça NGonzalez Boix E(2021)ECROs: building global scale systems from sequential codeProceedings of the ACM on Programming Languages10.1145/34854845:OOPSLA(1-30)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485484
Braun SDesloch S(2020)A Classification of Replicated Data for the Design of Eventually Consistent Domain Models2020 IEEE International Conference on Software Architecture Companion (ICSA-C)10.1109/ICSA-C50368.2020.00014(33-40)Online publication date: Mar-2020
https://doi.org/10.1109/ICSA-C50368.2020.00014
Vučković J(2019)You Are Not NetflixMicroservices10.1007/978-3-030-31646-4_13(333-346)Online publication date: 12-Dec-2019
https://doi.org/10.1007/978-3-030-31646-4_13
Bouajjani AEnea CGuerraoui RHamza J(2017)On verifying causal consistencyACM SIGPLAN Notices10.1145/3093333.300988852:1(626-638)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1145/3093333.3009888
Bouajjani AEnea CGuerraoui RHamza JCastagna GGordon A(2017)On verifying causal consistencyProceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages10.1145/3009837.3009888(626-638)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1145/3009837.3009888
Braun S(2017)Semantics-Driven Optimistic Data Replication: Towards a Framework Supporting Software Architects and Developers2017 IEEE International Conference on Software Architecture Workshops (ICSAW)10.1109/ICSAW.2017.18(236-241)Online publication date: Apr-2017
https://doi.org/10.1109/ICSAW.2017.18
de Almeida DHara CCiferri Rde Aguiar Ciferri C(2017)An asynchronous collaborative reconciliation model based on data provenanceSoftware: Practice and Experience10.1002/spe.250648:1(197-232)Online publication date: 13-Jun-2017
https://doi.org/10.1002/spe.2506
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Feasibility of online divergent thinking assessment

The effect of group composition on divergent thinking in an interaction design activity

The Effects of Generative AI on Design Fixation and Divergent Thinking