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.
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.
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.