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 th
...
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.