News for hackers. Stuff that matters.
Re:Ask HN: What is new in Algorithms / Data Structures these... by vivegi on Thursday May 11, 2023 @02:36AM (#35898523)
Are you using a rolling hash (such as the one employed in Rabin-Karp string search algorithm)? You can then store the hash at check points and the intermediate hashes between checkpoints can be regenerated using the rolling hash.

   +[h1] +[batch1] +[h2] [batch2] -[h3] +[batch3] +[h4]
You would then have the operations log for a replica as

   +[forwardhash(null)] +[hello] +[forwardhash(hello)] +[world] -[reversehash(world)] +[ ] +[forwardhash(wor) -[ld]+[k]
This sequence would give the following replica states after processing each hash:

   +[forwardhash(null)] +[hello] -> hello
   +[forwardhash(hello)] +[world] -> helloworld
   -[reversehash(world)] +[ ] -> hello world
   +[forwardhash(wor) -[ld]+[k] -> hello work
The direction of the roll is just a sign bit of the hash.

We don't need to encode positions separately as it is a function of the state of the replica and the sign of the hash.

There are no comments on this comment yet.