Conflict-Free Replicated Probabilistic Filter
J. XIONG (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Burcu Külahçıoğlu Özkan – Mentor (TU Delft - Software Engineering)
A. van Deursen – Graduation committee member (TU Delft - Software Engineering)
Jérémie Decouchant – Graduation committee member (TU Delft - Data-Intensive Systems)
E.B. Gulcan – Graduation committee member (TU Delft - Software Engineering)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Conflict-free replicated data types (CRDTs) offer high-availability low-latency updates to data without the need for central coordination. Despite the current vast collection of CRDTs, few works have been done on maintaining probabilistic membership information using CRDTs. In this thesis, we fill the gap by proposing conflict-free replicated probabilistic filters (CRPFs). The CRPFs provide probabilistic guarantees similar to that of the Bloom filter and the cuckoo filter, and allow for concurrent updates implementing grow-only and observed-remove semantics. We check their correctness by both paper proof and software verification. Our experiments demonstrate the performance of CRPFs in real-world settings regarding the empirical false positive rate and memory consumption.