Non-uniform replication

Gonçalo Cabrita, Nuno Preguiça

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Replication is a key technique in the design of efficient and reliable distributed systems. As information grows, it becomes difficult or even impossible to store all information at every replica. A common approach to deal with this problem is to rely on partial replication, where each replica maintains only a part of the total system information. As a consequence, a remote replica might need to be contacted for computing the reply to some given query, which leads to high latency costs particularly in geo-replicated settings. In this work, we introduce the concept of nonuniform replication, where each replica stores only part of the information, but where all replicas store enough information to answer every query. We apply this concept to eventual consistency and conflict-free replicated data types. We show that this model can address useful problems and present two data types that solve such problems. Our evaluation shows that non-uniform replication is more efficient than traditional replication, using less storage space and network bandwidth.

Original languageEnglish
Title of host publication21st International Conference on Principles of Distributed Systems, OPODIS 2017
EditorsJ. Aspnes, J. Leitão, A. Bessani, P. Felber
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume95
ISBN (Electronic)9783959770613
DOIs
Publication statusPublished - 1 Mar 2018
Event21st International Conference on Principles of Distributed Systems, OPODIS 2017 - Lisboa, Portugal
Duration: 18 Dec 201720 Dec 2017

Conference

Conference21st International Conference on Principles of Distributed Systems, OPODIS 2017
CountryPortugal
CityLisboa
Period18/12/1720/12/17

Fingerprint

Information systems
Bandwidth
Costs

Keywords

  • Eventual consistency
  • Non-uniform replication
  • Partial replication
  • Replicated data types

Cite this

Cabrita, G., & Preguiça, N. (2018). Non-uniform replication. In J. Aspnes, J. Leitão, A. Bessani, & P. Felber (Eds.), 21st International Conference on Principles of Distributed Systems, OPODIS 2017 (Vol. 95). [24] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.OPODIS.2017.24
Cabrita, Gonçalo ; Preguiça, Nuno. / Non-uniform replication. 21st International Conference on Principles of Distributed Systems, OPODIS 2017. editor / J. Aspnes ; J. Leitão ; A. Bessani ; P. Felber. Vol. 95 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018.
@inproceedings{b5195970c8d24b78a657d9545b701fc9,
title = "Non-uniform replication",
abstract = "Replication is a key technique in the design of efficient and reliable distributed systems. As information grows, it becomes difficult or even impossible to store all information at every replica. A common approach to deal with this problem is to rely on partial replication, where each replica maintains only a part of the total system information. As a consequence, a remote replica might need to be contacted for computing the reply to some given query, which leads to high latency costs particularly in geo-replicated settings. In this work, we introduce the concept of nonuniform replication, where each replica stores only part of the information, but where all replicas store enough information to answer every query. We apply this concept to eventual consistency and conflict-free replicated data types. We show that this model can address useful problems and present two data types that solve such problems. Our evaluation shows that non-uniform replication is more efficient than traditional replication, using less storage space and network bandwidth.",
keywords = "Eventual consistency, Non-uniform replication, Partial replication, Replicated data types",
author = "Gon{\cc}alo Cabrita and Nuno Pregui{\cc}a",
note = "info:eu-repo/grantAgreement/EC/H2020/732505/EU# info:eu-repo/grantAgreement/FCT/5876/147279/PT# CMU-Portugal research project GoLocal Ref. CMUP-ERI/TIC/0046/2014",
year = "2018",
month = "3",
day = "1",
doi = "10.4230/LIPIcs.OPODIS.2017.24",
language = "English",
volume = "95",
editor = "J. Aspnes and J. Leit{\~a}o and A. Bessani and P. Felber",
booktitle = "21st International Conference on Principles of Distributed Systems, OPODIS 2017",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

}

Cabrita, G & Preguiça, N 2018, Non-uniform replication. in J Aspnes, J Leitão, A Bessani & P Felber (eds), 21st International Conference on Principles of Distributed Systems, OPODIS 2017. vol. 95, 24, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 21st International Conference on Principles of Distributed Systems, OPODIS 2017, Lisboa, Portugal, 18/12/17. https://doi.org/10.4230/LIPIcs.OPODIS.2017.24

Non-uniform replication. / Cabrita, Gonçalo; Preguiça, Nuno.

21st International Conference on Principles of Distributed Systems, OPODIS 2017. ed. / J. Aspnes; J. Leitão; A. Bessani; P. Felber. Vol. 95 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. 24.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Non-uniform replication

AU - Cabrita, Gonçalo

AU - Preguiça, Nuno

N1 - info:eu-repo/grantAgreement/EC/H2020/732505/EU# info:eu-repo/grantAgreement/FCT/5876/147279/PT# CMU-Portugal research project GoLocal Ref. CMUP-ERI/TIC/0046/2014

PY - 2018/3/1

Y1 - 2018/3/1

N2 - Replication is a key technique in the design of efficient and reliable distributed systems. As information grows, it becomes difficult or even impossible to store all information at every replica. A common approach to deal with this problem is to rely on partial replication, where each replica maintains only a part of the total system information. As a consequence, a remote replica might need to be contacted for computing the reply to some given query, which leads to high latency costs particularly in geo-replicated settings. In this work, we introduce the concept of nonuniform replication, where each replica stores only part of the information, but where all replicas store enough information to answer every query. We apply this concept to eventual consistency and conflict-free replicated data types. We show that this model can address useful problems and present two data types that solve such problems. Our evaluation shows that non-uniform replication is more efficient than traditional replication, using less storage space and network bandwidth.

AB - Replication is a key technique in the design of efficient and reliable distributed systems. As information grows, it becomes difficult or even impossible to store all information at every replica. A common approach to deal with this problem is to rely on partial replication, where each replica maintains only a part of the total system information. As a consequence, a remote replica might need to be contacted for computing the reply to some given query, which leads to high latency costs particularly in geo-replicated settings. In this work, we introduce the concept of nonuniform replication, where each replica stores only part of the information, but where all replicas store enough information to answer every query. We apply this concept to eventual consistency and conflict-free replicated data types. We show that this model can address useful problems and present two data types that solve such problems. Our evaluation shows that non-uniform replication is more efficient than traditional replication, using less storage space and network bandwidth.

KW - Eventual consistency

KW - Non-uniform replication

KW - Partial replication

KW - Replicated data types

UR - http://www.scopus.com/inward/record.url?scp=85045669283&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.OPODIS.2017.24

DO - 10.4230/LIPIcs.OPODIS.2017.24

M3 - Conference contribution

VL - 95

BT - 21st International Conference on Principles of Distributed Systems, OPODIS 2017

A2 - Aspnes, J.

A2 - Leitão, J.

A2 - Bessani, A.

A2 - Felber, P.

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

ER -

Cabrita G, Preguiça N. Non-uniform replication. In Aspnes J, Leitão J, Bessani A, Felber P, editors, 21st International Conference on Principles of Distributed Systems, OPODIS 2017. Vol. 95. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2018. 24 https://doi.org/10.4230/LIPIcs.OPODIS.2017.24