Simple multi-party set reconciliation

DOI10.1007/s00446-017-0316-0zbMath1482.68059arXiv1311.2037OpenAlexW2964279644MaRDI QIDQ2075624

Rasmus Pagh, Michael Mitzenmacher

Publication date: 15 February 2022

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1311.2037

zbMATH Keywords

sketchinghashingset reconciliationmulti-partynetwork coding

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Cryptography (94A60) Distributed systems (68M14)

Uses Software

• GitHub
• Dynamo

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cores of random \(r\)-partite hypergraphs
• New gossips and telephones
• Size-estimation framework with applications to transitive closure and reachability
• Min-wise independent permutations
• Randomized algorithms for tracking distributed count, frequencies, and ranks
• A fuzzy vault scheme
• Almost tight bounds for rumour spreading with conductance
• Mixed Hypergraphs for Linear-Time Construction of Denser Hashing-Based Data Structures
• Gossip Algorithms
• Set reconciliation with nearly optimal communication complexity
• Space-Efficient Straggler Identification in Round-Trip Data Streams Via Newton’s Identities and Invertible Bloom Filters
• Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
• A survey of gossiping and broadcasting in communication networks
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Efficient erasure correcting codes
• Analyzing network coding gossip made easy

This page was built for publication: Simple multi-party set reconciliation