Упорядочение событий на основе векторных часов
У меня есть копии некоторой структуры данных и истории операций, которые произошли на ней. Каждая операция имеет метку времени с векторными часами.
Предположим, три векторных часов: VC(a) = <1, 0, 0>, VC(b) = <0, 1, 0> а также VC(c) = <1, 0, 3>, Мы можем заявить, что:
VC(a)случилось раньшеVC(c)VC(a)совпадает сVC(b)VC(b)совпадает сVC(c)
На основе a happened before c На самом деле мы знаем, что есть только три действительных заказа: bac, abc а также acb,
Как мы можем вычислить все действительные заказы программно? Я попытался отсортировать векторные часы, используя happened before как < компаратор. Однако проблема в том, что VC(a) !< VC(b) а также VC(b) !< VC(a) не означает, что VC(a) == VC(b) (это только подразумевает, что они параллельны), однако это то, на что полагаются алгоритмы сортировки.
Следовательно, сортировка вышеупомянутых векторных часов приведет к a b c или же a c b но нет b a c так как a < c и ошибочно c == b и поэтому a < b,
Я знаю, что могу вычислить все перестановки, а затем отфильтровать порядки, в которых одно из причинных отношений не соблюдается, однако это ужасно неэффективно, поскольку n! перестановки из n операций.
Я предполагаю, что проблема сортировки происходит из-за того, что я пытаюсь отсортировать частично упорядоченный набор?