# Pijul Pull Algorithm

**URL:** <https://discourse.pijul.org/t/pijul-pull-algorithm/894>\
**Category:** Question\
**Created:** [March 10, 2022, 10:49am UTC](https://discourse.pijul.org/t/pijul-pull-algorithm/894 "2022-03-10T10:49:43Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![burdiyan](https://yyz1.discourse-cdn.com/flex031/user_avatar/discourse.pijul.org/burdiyan/32/357_2.png) [@burdiyan](https://discourse.pijul.org/u/burdiyan)\
**Post date:** [March 10, 2022, 10:49am UTC](https://discourse.pijul.org/t/pijul-pull-algorithm/894/1 "2022-03-10T10:49:43Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![pmeunier](https://yyz1.discourse-cdn.com/flex031/user_avatar/discourse.pijul.org/pmeunier/32/4_2.png) [@pmeunier](https://discourse.pijul.org/u/pmeunier)\
**Post date:** [March 10, 2022, 1:22pm UTC](https://discourse.pijul.org/t/pijul-pull-algorithm/894/2 "2022-03-10T13:22:13Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![burdiyan](https://yyz1.discourse-cdn.com/flex031/user_avatar/discourse.pijul.org/burdiyan/32/357_2.png) [@burdiyan](https://discourse.pijul.org/u/burdiyan)\
**Post date:** [March 10, 2022, 9:33pm UTC](https://discourse.pijul.org/t/pijul-pull-algorithm/894/3 "2022-03-10T21:33:11Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![burdiyan](https://yyz1.discourse-cdn.com/flex031/user_avatar/discourse.pijul.org/burdiyan/32/357_2.png) [@burdiyan](https://discourse.pijul.org/u/burdiyan)\
**Post date:** [March 11, 2022, 4:08pm UTC](https://discourse.pijul.org/t/pijul-pull-algorithm/894/4 "2022-03-11T16:08:21Z")

</div>

> [@pmeunier](#):
>
> we first synchronise a cached version of the remote log

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?

---

<div class="post-metadata">

**Author:** ![joyously](https://yyz1.discourse-cdn.com/flex031/user_avatar/discourse.pijul.org/joyously/32/266_2.png) [@joyously](https://discourse.pijul.org/u/joyously)\
**Post date:** [March 11, 2022, 4:14pm UTC](https://discourse.pijul.org/t/pijul-pull-algorithm/894/5 "2022-03-11T16:14:52Z")

</div>

I was asking a similar thing over at Zulip: [two similar repos](https://pijul.zulipchat.com/#narrow/stream/270693-general/topic/two.20similar.20repos/near/273415986)

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.

---

<div class="post-metadata">

**Author:** ![pmeunier](https://yyz1.discourse-cdn.com/flex031/user_avatar/discourse.pijul.org/pmeunier/32/4_2.png) [@pmeunier](https://discourse.pijul.org/u/pmeunier)\
**Post date:** [March 11, 2022, 7:48pm UTC](https://discourse.pijul.org/t/pijul-pull-algorithm/894/6 "2022-03-11T19:48:47Z")

</div>

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