Синхронизация двух упорядоченных списков

У нас есть две автономные системы, которые обычно не могут общаться друг с другом. Обе системы поддерживают один и тот же упорядоченный список элементов. Только в редких случаях они смогут общаться друг с другом для синхронизации списка.

Элементы помечаются отметкой времени модификации для обнаружения правок. Элементы идентифицируются по UUID, чтобы избежать конфликтов при вставке новых элементов (, в отличие от использования автоматического-увеличения целых чисел). При синхронизации новые UUID обнаруживаются и копируются в другую систему. Аналогично для удалений.

Приведенная выше структура данных подходит для неупорядоченного списка, но как мы можем управлять упорядочением? Если бы мы добавили целочисленный «ранг», то это потребовало бы перенумерации при вставке нового элемента (, что потребовало бы синхронизации всех последующих элементов из-за только 1 вставки). В качестве альтернативы, мы могли бы использовать дробные ранги (использовать среднее рангов элемента-предшественника и элемента-последователя), но это не кажется надежным решением, поскольку оно быстро столкнется с проблемами точности, когда будет вставлено много новых элементов..

Мы также рассматривали возможность реализации этого в виде двусвязного-списка, в котором каждый элемент содержит UUID своего предшественника и элемента-преемника. Однако для этого по-прежнему потребуется синхронизировать 3 элемента при вставке 1 нового элемента (или синхронизировать 2 оставшихся элемента при удалении 1 элемента).

Предпочтительно, мы хотели бы использовать структуру данных или алгоритм, в котором необходимо синхронизировать только вновь вставленный элемент. Существует ли такая структура данных?

Редактировать:мы также должны уметь перемещать существующий элемент в другую позицию!