eCommons

 

Set Reconciliation with Nearly Optimal Communication Complexity

dc.contributor.authorMinsky, Yaronen_US
dc.contributor.authorTrachtenberg, Arien_US
dc.contributor.authorZippel, Richarden_US
dc.date.accessioned2007-04-09T19:49:07Z
dc.date.available2007-04-09T19:49:07Z
dc.date.issued2000-09-27en_US
dc.description.abstractWe consider the problem of efficiently reconciling two similar sets held by different hosts while minimizing the communication complexity. This type of problem arises naturally from gossip protocols used for the distribution of information. We describe an aproach to set reconciliation based on the encoding of sets as polynomials. The resulting protocols exhibit tractable computational complexity and nearly optimal communication complexity. Also, these protocols can be adapted to work over a broadcast channel, allowing many clients to reconcile with one host based on a single broadcast, even if each client is missing a different subset.en_US
dc.format.extent308955 bytes
dc.format.extent346644 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR2000-1813en_US
dc.identifier.urihttps://hdl.handle.net/1813/5803
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleSet Reconciliation with Nearly Optimal Communication Complexityen_US
dc.typetechnical reporten_US

Files

Original bundle
Now showing 1 - 2 of 2
Loading...
Thumbnail Image
Name:
2000-1813.pdf
Size:
301.71 KB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
2000-1813.ps
Size:
338.52 KB
Format:
Postscript Files