Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Informatik

Probevortrag zur Dissertation: Nico Kruber

  • Wann 16.11.2016 von 10:15 bis 11:30
  • Wo 12489 Berlin, Rudower Chaussee 25, Humboldt-Kabinett
  • iCal

Herr Sven Nico Kruber wird einen Probevortrag zu seiner Dissertation halten zum Thema

"Approximate Distributed Set Reconciliation with Defined Accuracy"


Alle Interesseneten sind herzlich eingeladen!



The objective comparison of approximate versioned set reconciliation algorithms is challenging. Each algorithm's behavior can be tuned for a given use case, e.g. low bandwidth or computational overhead, using different sets of parameters. Changes on these parameters, however, often also influence the algorithm's accuracy in recognizing differences between two sets and thus hinder objective comparisons.

We develop a method to fairly compare approximate set reconciliation algorithms by enforcing a fixed accuracy and deriving accuracy-influencing parameters accordingly. We show this method's universal applicability by adopting two trivial hash-based algorithms as well as set reconciliation with Bloom filters and Merkle trees. Compared to previous research on Merkle trees, we propose to use dynamic hash sizes to align the transfer overhead with the desired accuracy. An extensive evaluation of each algorithm under this accuracy model verifies its feasibility and ranks these four algorithms.

Our results allow to easily choose an efficient algorithm for practical set reconciliation tasks based on the required level of accuracy. Our way to find equally accurate configuration parameters for different algorithms can also be adopted to other set reconciliation algorithms and allows to rate their respective performance in an objective manner. The resultant new approximate Merkle tree reconciliation broadens the applicability of Merkle trees and sheds some new light on its parameters.