Pijul Pull Algorithm

I’ve been trying to find some information about how Pijul decides what changes it needs to pull from a remote, but I couldn’t find any details. Could someone point me somewhere where I could learn more about it?

I guess Pijul somehow exchanges a set of Head patches with each other, and from there figures out what patches are missing on each end. Is there a description of this algorithm somewhere?

The description is the code itself at the moment. This isn’t totally easy: we first synchronise a cached version of the remote log, using elliptic curve algebra to account for patch commutation. Then we compare the logs since the last common state.

This can be very dumb sometimes, like for example if you have one very old patch you never pushed, things can be compared over and over again. Hopefully since comparisons are always done on the local machine, and take linear time in the size of history in the worst case, even that case won’t be take too long.

And this algorithm is usually surprisingly fast, especially for the task it has to accomplish (synchronise unordered sets).

Thanks for a fast response! I’ll try to dig deeper into the code to understand it better.

I have a question about that. When you say remote log, what exactly this log contains? I thought there’s no linear history in Pijul, but when you say “log” I assume some append-only or at least linear nature. Do clients keep any logs that is used for syncing in any way?

I was asking a similar thing over at Zulip: two similar repos

My humble opinion is that the changes should always maintain their original date, and that date should be used in the log command by default, with options to use a different order. Comparing things is always easier when they are ordered.

The log is ordered, actually, but it can be edited almost arbitrarily, for example by unrecording patches other than the last one.