On Feb 25, 2010, at 7:22 AM, Yaron Minsky wrote:
The use of the prefix tree is described in the two articles Set
Reconciliation with Nearly Optimal Communication Complexity and
Practical Set Reconciliation. You will find them on the Google code
page¹. The mathematics are quite involved though. It is the
information that is needed for two servers to know what keys they need
to exchange.
Indeed. The data structure is called a prefix-tree in the paper (hence PTree). Basically, it's a binary tree that holds a special kind of checksum for different subsets of the keyspace, dividing the space of keys up as you go down the tree.
The partition tree in section 4 of "Practical Set Reconciliation"? That looks like what you are describing.
Thanks!
73 de Jeff
|