Hugo Rafael Silva Guerreiro

Co-advisor: Prof. N. Preguiça

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.


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.


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