Учитывая, что каждый пэр действует индивидуально в вашем случае, это не значит, что только один автомат решает вашу проблему, но многие.Поскольку выборка блока данных, когда он недоступен в течение заданной задержки, как правило, является полиномиальной проблемой, и, поскольку задание выполняется отдельными узлами, проблема не является проблемой NP для каждого узла локально.
Вкл.С другой стороны, если серверу необходимо вычислить минимальное распределение ресурсов резервного копирования для передачи «отсутствующих блоков», вам сначала нужно узнать о вероятности того, что одноранговый узел пропустит блок (например, среднее + стандартное отклонение).Предполагая, что вы знаете статистическое распределение таких событий, вы можете вычислить общую полосу пропускания, необходимую для передачи этих недостающих блоков с выбранным риском отказа / допустимого отклонения в полосе пропускания.Если вы используете несколько серверов для удовлетворения потребностей, убедитесь, что ваши коллеги связываются с ними случайным образом для распределения нагрузки.
Решение этой статистической проблемы не является проблемой NP.Вы можете собирать информацию об ошибках от каждого узла и добавлять ее на центральном / серверном узле.Поэтому я пришел к выводу, что ваша проблема не является проблемой NP.
ЧАСТЬ II:
О, теперь я понимаю ваш случай лучше: несколько «серверных» пиров потенциально могут помочь одному пиру получитьполный блок.В этом случае количество серверных пиров в вашей системе растет экспоненциально для данного блока.В этом случае эта проблема оптимизации имеет все характерные для меня проблемы затопления, и они являются NP.
Даже если ваш график пиров и потенциальных связей между ними был статическим (что никогда не случалось вреальной P2P-сети), вычисление оптимального решения за разумное количество времени для более чем 50 или 100 узлов практически невозможно, если вы не можете сделать очень конкретные предположения на этом графике (что почти никогда не бывает в общем случае и не всегда полезно).
Но вам абсолютно необходимо иметь абсолютно оптимальное решение или оно достаточно близко к оптимальному?
Эвристика подскажет вам, что если у ваших пиров более или менее одинаковая пропускная способность при загрузкетогда имеет смысл сначала обслуживать одноранговые узлы с самой высокой пропускной способностью UPLOAD, чтобы максимизировать лавинный эффект и снизить риск того, что одноранговый узел должен будет обратиться за помощью, в общем.
Если ваш график относительно сбалансирован (этобольшинство пэров могут подключиться кя полагаю, что минимальная пропускная способность исходных серверов будет логарифмической функцией числа узлов в вашем графике, умноженного на среднюю скорость, с которой ожидают обслуживаемые узлы.Это только мое внутреннее чувство, и оно должно быть подтверждено реальными мерами или тщательным моделированием вашего дела.