Фильтр Блума для эффективной синхронизации хеш-графов

В одном из совместных исследований нам с Хайди требовалось решить такую задачу. Допустим, нам требуется синхронизировать между двумя узлами хеш-граф, например, как в репозитории Git. В Git каждый коммит идентифицируется через соответствующий ему хеш, причём, в коммит могут включаться хеши коммитов-предшественников (то есть, конкретный коммит может содержать более одного хеша, если он получен слиянием). Мы хотели получить минимальное множество таких коммитов, которыми должны обменяться два узла, чтобы их графы получились одинаковыми.