Set union is one of the most fundamental mathematical operations. Improving on prior work by Eppstein and Dold, this thesis presents a network protocol and implementation to efficiently compute the set union over a network.
When computing a set union, it is possible that the sets have a large overlap and that the actual difference between the sets is small. In these cases, it can be inefficient to simply transfer all elements to compute the set union. Eppstein proposed a protocol to reconcile two sets that required resources proportional to the set size difference.
The goal of the thesis is to review, improve and document the existing implementation by Dold of the "Byzantine Fault Tolerant Set Reconciliation", which is a variant on Eppstein's original proposal used for key revocation in the GNU Name System. Other possible applications for the technology include e-voting systems, where a consensus must be established on the set of submitted ballots between the voting authorities.