Hugo Rafael Silva Guerreiro
Causality Tracking Trade-offs for Distributed Storage
Tese submetida para provas de mestrado em Engenharia
Informática e de Computadores Instituto Superior
Técnico, Universidade de Lisboa.
Abstract
After the seminal paper by L. Lamport, which introduced (scalar)
logical clocks, several other data structures for keeping track of
causality in distributed systems have been proposed, including vector
and matrix clocks. These are able to capture causal dependencies with
more detail but, unfortunately, also consume a substantially larger
amount of network bandwidth and storage space than Lamport
clocks. This raises the question of whether the benefits of these more
complex structures are worth their cost. We address this question in
the context of partially replicated systems. We show that for some
workloads the use of more expensive clocks does bring significant
benefits and that for other workloads no visible benefits can be
observed. In this thesis, we provide a characterization of the
scenarios where each type of clock is more beneficial, helping
designers to develop more efficient distributed storage systems.
Publicações
- Causality Tracking Trade-offs for Distributed Storage
- Hugo Rafael Silva Guerreiro
- MSc Thesis. Instituto Superior
Técnico, Universidade de Lisboa.
- November, 2020.
- Available BibTeX, MSC Thesis, and extended abstract, and mid-term
report.
- Causality Tracking Tradeoffs for Distributed
Storage.
- H. Guerreiro, L. Rodrigues, N. Preguiça
and N. Quental.
- Proceedings of the 19th IEEE International
Symposium on Network Computing and Applications (NCA), Online,
November 2020.
-
Presentation
video
Luís Rodrigues