Article

Concise version vectors in WinFS

Authors:

Dahlia Malkhi,

Doug TerryAuthors Info & Claims

DISC'05: Proceedings of the 19th international conference on Distributed Computing

Pages 339 - 353

https://doi.org/10.1007/11561927_25

Published: 26 September 2005 Publication History

Publisher Site

Abstract

Conflicts naturally arise in optimistically replicated systems. The common way to detect update conflicts is via version vectors, whose storage and communication overhead are number of replicas × number of objects. These costs may be prohibitive for large systems.

This paper presents predecessor vectors with exceptions (PVEs), a novel optimistic replication technique developed for Microsoft’s WinFS system. The paper contains a systematic study of PVE’s performance gains over traditional schemes. The results demonstrate a dramatic reduction of storage and communication overhead in normal scenarios, during which communication disruptions are infrequent. Moreover, they identify a cross-over threshold in communication failure-rate, beyond which PVEs loses efficiency compared with traditional schemes.

References

[1]

D. S. Parker (Jr.), G. J. Popek, G. Rudisin, A. Stoughton, B. J. Walker, E. Walton, J. M. Chow, S. Kiser D. Edwards, and C. Kline. Detection of mutual inconsistency in distributed systems. IEEE Transactions on Software Engineering, 9(3):240-247, May 1983.

Digital Library

Google Scholar

[2]

T. W. Page (Jr.), R. G. Guy, J. S. Heidemann, D. H. Ratner, P. L. Reiher, A. Goel, G. H. Kuenning, and G. Popek. Perspectives on optimistically replicated peer-to-peer filing. Software - Practice and Experience, 11(1), December 1997.

Digital Library

Google Scholar

[3]

R. Ladin, B. Liskov, L. Shrira, and S. Ghemawat. Providing high availability using lazy replication. ACM Transactions on Computer Systems, 10(4):360-391, 1992.

Digital Library

Google Scholar

[4]

D. H. Ratner. Roam: A Scalable Replication System for Mobile and Distributed Computing. PhD thesis, 1998. UCLA Technical report UCLA-CSD-970044.

Digital Library

Google Scholar

Cited By

View all

Fernandes PBaquero CGonzalez Boix ESutra P(2023)Probabilistic Causal Contexts for Scalable CRDTsProceedings of the 10th Workshop on Principles and Practice of Consistency for Distributed Data10.1145/3578358.3591331(1-8)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3578358.3591331
Gonçalves RAlmeida PBaquero CFonte V(2015)Concise Server-Wide Causality Management forźEventually Consistent Data StoresProceedings of the 15th IFIP WG 6.1 International Conference on Distributed Applications and Interoperable Systems - Volume 903810.1007/978-3-319-19129-4_6(66-79)Online publication date: 2-Jun-2015
https://dl.acm.org/doi/10.1007/978-3-319-19129-4_6
Almeida PBaquero CGonçalves RPreguiça NFonte V(2014)Scalable and Accurate Causality Tracking for Eventually Consistent StoresProceedings of the 14th IFIP WG 6.1 International Conference on Distributed Applications and Interoperable Systems - Volume 846010.1007/978-3-662-43352-2_6(67-81)Online publication date: 3-Jun-2014
https://dl.acm.org/doi/10.1007/978-3-662-43352-2_6
Show More Cited By

Index Terms

Concise version vectors in WinFS
1. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles

Recommendations

Concise version vectors in WinFS

Conflicts naturally arise in optimistically replicated systems. The common way to detect update conflicts is via version vectors, whose storage and communication overhead are number of replicas number of objects. These costs may be prohibitive for large ...
Single-version STMs can be multi-version permissive
ICDCN'11: Proceedings of the 12th international conference on Distributed computing and networking

We present PermiSTM, a single-version STM that satisfies a practical notion of permissiveness, usually associated with keeping many versions: it never aborts read-only transactions, and it aborts other transactions only due to a conflicting transaction (...
A TimeStamp Based Multi-version STM Algorithm
ICDCN 2014: Proceedings of the 15th International Conference on Distributed Computing and Networking - Volume 8314

Software Transactional Memory Systems STM are a promising alternative for concurrency control in shared memory systems. Multiversion STM systems maintain multiple versions for each t-object. The advantage of storing multiple versions is that it ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DISC'05: Proceedings of the 19th international conference on Distributed Computing

September 2005

518 pages

ISBN:3540291636

Editor:
Pierre Fraigniaud
CNRS and University Paris Diderot

In-Cooperation

Warsaw Univ.: Warsaw University
Jagiellonian Univ.: Jagiellonian University

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 26 September 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Fernandes PBaquero CGonzalez Boix ESutra P(2023)Probabilistic Causal Contexts for Scalable CRDTsProceedings of the 10th Workshop on Principles and Practice of Consistency for Distributed Data10.1145/3578358.3591331(1-8)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3578358.3591331
Gonçalves RAlmeida PBaquero CFonte V(2015)Concise Server-Wide Causality Management forźEventually Consistent Data StoresProceedings of the 15th IFIP WG 6.1 International Conference on Distributed Applications and Interoperable Systems - Volume 903810.1007/978-3-319-19129-4_6(66-79)Online publication date: 2-Jun-2015
https://dl.acm.org/doi/10.1007/978-3-319-19129-4_6
Almeida PBaquero CGonçalves RPreguiça NFonte V(2014)Scalable and Accurate Causality Tracking for Eventually Consistent StoresProceedings of the 14th IFIP WG 6.1 International Conference on Distributed Applications and Interoperable Systems - Volume 846010.1007/978-3-662-43352-2_6(67-81)Online publication date: 3-Jun-2014
https://dl.acm.org/doi/10.1007/978-3-662-43352-2_6
Du JElnikety SRoy AZwaenepoel WLohman G(2013)OrbeProceedings of the 4th annual Symposium on Cloud Computing10.1145/2523616.2523628(1-14)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1145/2523616.2523628
Belaramani NZheng JNayate ASoulé RDahlin MGrimm RRexford JSirer E(2009)PADSProceedings of the 6th USENIX symposium on Networked systems design and implementation10.5555/1558977.1558982(59-73)Online publication date: 22-Apr-2009
https://dl.acm.org/doi/10.5555/1558977.1558982
Salmon BSchlosser SCranor LGanger G(2009)PerspectiveProccedings of the 7th conference on File and storage technologies10.5555/1525908.1525921(167-182)Online publication date: 24-Feb-2009
https://dl.acm.org/doi/10.5555/1525908.1525921
Chaitanya SSarkar PWang XShroff N(2008)CD-PANProceedings of the 4th Annual International Conference on Wireless Internet10.5555/1554126.1554154(1-11)Online publication date: 17-Nov-2008
https://dl.acm.org/doi/10.5555/1554126.1554154
Rowstron ASadekar VSanti PHu YMauve M(2008)Understanding the content lifecycle in vehicular applicationsProceedings of the fifth ACM international workshop on VehiculAr Inter-NETworking10.1145/1410043.1410057(76-77)Online publication date: 15-Sep-2008
https://dl.acm.org/doi/10.1145/1410043.1410057
Bjørner N(2007)Models and software model checking of a distributed file replication systemFormal methods and hybrid real-time systems10.5555/1793874.1793875(1-23)Online publication date: 1-Jan-2007
https://dl.acm.org/doi/10.5555/1793874.1793875
Malkhi DNovik LPurcell C(2007)P2P replica synchronization with vector setsACM SIGOPS Operating Systems Review10.1145/1243418.124342741:2(68-74)Online publication date: 1-Apr-2007
https://dl.acm.org/doi/10.1145/1243418.1243427
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations