News for hackers. Stuff that matters.
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.

There are no comments on this comment yet.