DSys RG Late Sept 2022: What’s the Difference? (2011)

Paper: What’s the Difference? Efficient Set Reconciliation without Prior Context (2011)

00:04:22	Sodium :	<3
00:04:54	Quinn Wilton:	https://www.ics.uci.edu/~eppstein/pubs/EppGooUye-SIGCOMM-11.pdf
00:04:55	Philipp Krüger:	https://www.ics.uci.edu/~eppstein/pubs/EppGooUye-SIGCOMM-11.pdf
00:09:42	Michael Mure:	I have to say, reading that paper was really enjoyable. Even after understanding how it works, it still feels like cheating on the universe. Thanks for running that group :-)
00:10:03	Quinn Wilton:	"cheating on the universe" 🤣
00:12:44	Michael Mure:	well, you put elements in the IBF way way past the saturation point, yet somehow retrieve data from data, looks like they didn't hear about Shannon's information theory
00:16:07	Marc-Antoine Parent:	I imagine you can maintain the strata of IBF in memory continuously at low-ish cost; so computation cost is distributed
00:16:35	Brooklyn Zelenka (@expede):	👏👏👏
00:17:18	Zeeshan Lakhani:	Btw, fantastic summary of the paper.
00:17:30	Marc-Antoine Parent:	Indeed!
00:18:38	Eleanor (they/them):	I think Figure 5 shows how Shannon catches up to them
00:20:31	Sodium :	re: cheating on the universe, i am always blown away by the sorts of shenanigans you can pull off with xor
00:21:19	Michael Mure:	^ not really, you can still cram a billion elements in a tiny IBF and still recover the diff set from the mashed up bits
00:21:24	Brooklyn Zelenka (@expede):	@Sodium — XOR is magic ✨
00:21:34	Zeeshan Lakhani:	Agree, XOR is magic
00:21:43	Steve Moyer:	re: xor - <3 for CRCs (feed in some data - get a value ... feed in the same data - get zero)
00:39:36	Marc-Antoine Parent:	http://vldb.org/pvldb/vol14/p458-gong.pdf
00:46:56	Quinn Wilton:	Sorry, I thought you had finished :)
00:47:35	Brooklyn Zelenka (@expede):	Core use case
00:58:15	Jagan:	isn't this process known as Stochastic averaging?