按年被提到
20192019 · 1 次2026
系统、数据库与网络›分布式数据与 CRDT·arXiv:1910.07782 · cs.DS

The Distributed Bloom Filter

Lum Ramabaja, Arber Avdullahu · 2019
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2019-10-18 · 最近 2020-02-20
2不同的人
2活跃月份
2讨论串
6被引(OpenAlex)
arXiv 摘要(候选层不写导读)

The Distributed Bloom Filter is a space-efficient, probabilistic data structure designed to perform more efficient set reconciliations in distributed systems. It guarantees eventual consistency of states between nodes in a system, while still keeping bloom filter sizes as compact as possible. The eventuality can be tweaked as desired, by tweaking the distributed bloom filter's parameters. The scalability, as well as accuracy of the data structure is made possible by combining two novel ideas: The first idea introduces a new, computationally inexpensive way for populating bloom filters, making it possible to quickly compute new bloom filters when interacting with peers. The second idea introduces the concept of unique bloom filter mappings between peers. By applying these two simple ideas, one can achieve incredibly bandwidth-efficient set reconciliation in networks. Instead of trying to minimize the false positive rate of a single bloom filter, we use the unique bloom filter mappings to increase the probability for an element to propagate through a network. We compare the standard bloom filter with the distributed bloom filter and show that even with a false positive rate of 50%, i.e. even with a very small bloom filter size, the distributed bloom filter still manages to reach complete set reconciliation across the network in a highly space-efficient, as well as time-efficient way.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论krcz · 2020-02

“You still need one hash for every non-leaf node, so 30-40 hashes of 256 bits each. What this algorithm saves is 30-40 indices, which is 11 bits each for a 1000-leaf tree. Even aligning to 16 bits it's doesn't seem a great optimization. Unless I misunderstood something and we are not trying to minimize the size of whole proof, but just its structure - but…”

The Compact Merkle Multiproof原评论 ↗
被提交为 story · 1 次