Please use this identifier to cite or link to this item: https://hdl.handle.net/1822/62225

Full metadata record
DC FieldValueLanguage
dc.contributor.advisorBaquero, Carlospor
dc.contributor.advisorLeitão, João Carlos Antunespor
dc.contributor.authorDuarte, Vitor Manuel Enespor
dc.date.accessioned2019-11-19T11:30:51Z-
dc.date.available2019-11-19T11:30:51Z-
dc.date.issued2017-
dc.date.submitted2017-
dc.identifier.urihttps://hdl.handle.net/1822/62225-
dc.descriptionDissertação de mestrado em Computer Sciencepor
dc.description.abstractData consistency often needs to be sacrificed in order to ensure high-availability in large scale distributed systems. Conflict-free Replicated Data Types relax consistency by always allowing query and update operations at the local replica without remote synchronization. Consistency is then re-established by a background mechanism that synchronizes the replicas in the system. In state-based CRDTs replicas synchronize by periodically sending their local state to other replicas and by merging the received remote states with the local state. This synchronization can become very costly and unacceptable as the local state grows. Delta-state-based CRDTs solve this problem by producing smaller messages to be propagated. However, it requires each replica to store additional metadata with the messages not seen by its direct neighbors in the system. This metadata may not be available after a network partition, since a replica can be forced to garbage-collect it (due to storage/memory limitations), or when the set of direct neighbors of a replica changes (due to dynamic memberships). In this dissertation we further improve the synchronization of state-based CRDTs, by introducing the concept of Join Decomposition of a state-based CRDT and explaining how it can be used to reduce the synchronization cost of this variant of CRDTs. We validate our proposal experimentally on Google Cloud Platform by comparing the state-based synchronization algorithm against the classic and improved versions of the delta-state-based algorithm. The results of this comparison show that our proposed techniques can greatly reduce state transmission, even under normal operation when the network is stable.por
dc.description.abstractFrequentemente a consistência dos dados é sacrificada para garantir alta-disponibilidade em sistemas distribuídos de grande escala. Conflict-free Replicated Data Types relaxam a consistência permitindo operações de query e update na réplica local sem sincronização remota. Nos state-based CRDTs as réplicas sincronizam periodicamente enviando o seu estado local para as outras réplicas e combinando os estados remotos recebidos com o estado local. Esta sincronização pode tornar-se muito custosa e inaceitável à medida que o estado local cresce. Delta-state-based CRDTs resolvem este problema produzindo mensagens mais pequenas para serem propagadas. No entanto, requer guardar metadados adicionais com as mensagens que ainda não foram vistas pelos vizinhos diretos no sistema. Estes metadados podem não estar disponíveis depois de uma partição na rede, visto que a réplica pode ser forçada a apagá-los (devido a limitações de armazenamento/memória), ou quando o conjunto dos vizinhos diretos da réplica muda (devido a vistas dinâmicas). Nesta dissertação melhoramos ainda mais a sincronização de state-based CRDTs, introduzindo o conceito de Join Decomposition de um state-based CRDT e explicando como é que pode ser usado para reduzir o custo de sincronização desta variante de CRDTs. Validamos a nossa proposta experimentalmente na Google Cloud Platform comparando o algoritmo de sincronização de state-based CRDTs com a clássica e melhoradas versões do algoritmo dos delta-state-based. Os resultados desta comparação mostram que as técnicas propostas podem reduzir muito a transmissão de dados, mesmos em operação normal quando a rede está estável.por
dc.language.isoengpor
dc.rightsopenAccesspor
dc.titleEfficient synchronization of state-based CRDTspor
dc.typemasterThesiseng
dc.identifier.tid202301982por
thesis.degree.grantorUniversidade do Minhopor
sdum.degree.grade17 valorespor
sdum.uoeiEscola de Engenhariapor
dc.subject.fosEngenharia e Tecnologia::Outras Engenharias e Tecnologiaspor
Appears in Collections:BUM - Dissertações de Mestrado
DI - Dissertações de Mestrado

Files in This Item:
File Description SizeFormat 
Vítor-Manuel-Enes-Duarte-dissertação-final.pdf1,04 MBAdobe PDFView/Open

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu ORCID