Учитывая набор из M несинхронизированных реплик, как нам найти подмножество заданного размера N, которое минимизирует количество повторных передач сообщений, необходимых для синхронизации их состояний сообщений в надежной многоадресной среде (т. е. все реплики надежно получают сообщения всех других реплик)?
Состояния сообщений реплик состоят из сообщений, которые каждая из них имеет из одних и тех же D источников (D >= M). Для каждого источника реплика содержит все сообщения из этого источника до некоторого старшего порядкового номера (т. е. FIFO, без дыр, начиная с нуля). Таким образом, состояние сообщения реплики может быть представлено в виде вектора порядковых номеров, где каждый элемент соответствует источнику. В качестве альтернативы вы можете думать о состоянии сообщения реплики как о точке в D-мерном пространстве, если хотите.
Предположим, что все M реплик уже обменялись своими векторами состояний сообщений, поэтому все они имеют матрицу M строк x D столбцов всех своих состояний сообщений. Итак, теперь это чисто централизованная вычислительная задача с учетом этой матрицы.
Подход грубой силы, дающий оптимальный ответ, заключается в проверке всех (M выберите N) подмножеств и выборе того, который требует минимального количества повторных передач, необходимых для синхронизации этого подмножества. Проблема в том, что этот подход выглядит как факториальная асимптотическая сложность в M.
Я хотел посмотреть, знает ли кто-нибудь или может придумать оптимальный алгоритм с гораздо лучшими асимптотическими оценками?
Первоначально я думал о том, чтобы решить эту проблему как проблему теории графов с состояниями сообщений реплик, являющимися вершинами в полностью связанном графе, где веса ребер были манхэттенским расстоянием между векторами состояния сообщений двух конечных точек. Затем сделайте что-то вроде агломеративной иерархической кластеризации с минимальными связями, используя алгоритм Прима, за которым следует алгоритм Крускала, где мы останавливаемся, когда размер любого кластера равен или превышает N.
Это может выполняться за время O(M^2), но я могу построить встречные примеры, где это не дает немедленного оптимального ответа. Например, при D = 1 для простоты пусть M = 7 порядковых номеров реплик будут {0, 2, 4, 14, 15, 16, 19} и N = 5. Алгоритм Крускала сгруппирует {14, 15, 16 , 19 } и { 0, 2, 4 }, а затем соедините эти два кластера вместе на последнем шаге. Но реальный ответ, который мы хотели, — синхронизировать реплики со состояниями { 2, 4, 14, 15, 16 } вместе. Может быть, мы могли бы остановиться, когда первый объединенный кластер превысит N, а затем попытаться его обрезать? Но в этом примере мы снова возвращаемся к исходному вопросу, поскольку кластер, на котором мы остановились, фактически содержит все M реплик! И, конечно же, эта проблема не так проста, когда D > 1, что всегда будет (D >= M).
Другая проблема с описанным выше подходом заключается в том, что если алгоритм решит синхронизировать два кластера реплик в более крупный кластер, то это не только повлияет на расстояния между другими кластерами и вновь объединенным кластером (например, как в обычной агломеративной иерархической кластеризации), но и также расстояния между всеми другими кластерами, потому что все они слышат и могут извлечь выгоду из любых отправленных повторных передач. Таким образом, все расстояния между всеми кластерами могут меняться после каждого шага слияния и не таким простым образом, если вы позволяете реплике получать выгоду от сообщений, полученных здесь не в порядке FIFO, без дыр. Например, реплика A содержит сообщения от источника D1 до порядкового номера X. Алгоритм выбирает для синхронизации два кластера реплик, ни один из которых не включает A, для которых требуется повторная передача сообщений от источника D1 от X+5 до X+10. Оптимальный алгоритм должен понимать, что A потенциально выигрывает от этих повторных передач, даже если они выходят за пределы его FIFO, порядкового номера без дыр для источника D1 с промежутком между сообщениями от X+1 до X+4.
Другой способ, которым я думал о решении этой проблемы, заключался в том, чтобы рассматривать ее как геометрическую проблему, в которой состояния M реплик представляют точки в D-мерном пространстве L1. Затем мы хотим найти наименьшую «объемную» выпуклую оболочку, содержащую не менее N точек. Возможно, на самом деле это не очень хороший подход, но если подумать об этом с геометрической точки зрения, то естественно возникает идея о том, что все реплики могут выиграть от синхронизации любых двух наборов реплик. Большая часть их расстояний будет уменьшена до поверхности нового объекта (не вершины!), созданной слиянием состояний двух наборов.
РЕДАКТИРОВАТЬ. Еще один способ, которым я думал об этом, исходил из примера, который я привел. Для каждого исходного DX найдите подмножество из N реплик, которое требует минимального количества повторных передач для синхронизации на этом источнике. Это достаточно легко. Проблема в том, что вам придется сравнивать и модифицировать эти D подмножества, чтобы все они покрывали одни и те же N реплик. Это не полностью сформированная идея, потому что минимум N в каждом измерении DX является локальным минимумом в глобальном пространстве, который может быть не в той области, что и глобально оптимальный ответ для этого измерения. В любом случае, это еще одна идея для размышления.
EDIT2. Возвращаясь к алгоритму Прима + Крускала и игнорируя то, что каждое слияние обновляет относительные расстояния между всеми кластерами, верно ли, что когда мы обнаруживаем первый кластер, размер которого равен или превышает N, тогда оптимальный ответ должен быть некоторым подмножеством тот кластер? Если размер кластера равен N, то мы закончили. Если размер кластера превышает N, можем ли мы сделать что-то вроде вычисления центроида кластера и выбрать N реплик, ближайших к центроиду? Даст ли это оптимальный ответ? Это все еще кажется неправильным, потому что не учитывает «направленность» различных расстояний от центроида. То есть он не делает различий между двумя репликами, которые находятся близко друг к другу в D-мерном пространстве (которое ему следует отдавать предпочтение), в отличие от двух реплик, которые находятся в «противоположных» направлениях друг от друга относительно центроида. Может быть, вместо этого мы могли бы посмотреть на минимальное остовное дерево реплик в кластере и каким-то образом эффективно сократить его, чтобы найти подмножество минимального веса, которое остается связанным?
Будем очень признательны за любые идеи или указатели на соответствующие алгоритмы!
