Re:Scuttlebutt social network: a decentralised platform
by hinkley on Saturday February 24, 2024 @06:00PM
(#39495925)
Not in crypto, but it’s a linked list structure with a logarithmic number of additional pointers that refer forward (or in the case of a diff algorithm, backward) into the list, to provide closer to log n lookup time.
I think they were invented by Bill Pugh, a professor who also had some noteworthiness in Java concurrency fifteen years ago, which is how I heard of them.
Wikipedia agrees (W Pugh for William)
https://en.wikipedia.org/wiki/Skip_list
So the way I see it, you’d overlay the linear tree with one that refers to a single, recent hash, a much older hash (or another meta node of the same degree) and a roll up delta from that older hash, with a new hash that satisfies both. Then every time the number of records double, you add another layer over the previous one.
Do you have any references or reading material on this pattern? Would love to learn more.