Здравствуйте, Кодт, Вы писали:

[]

К>Тогда вот ещё такой вопрос: сколько серверов одновременно могут быть выключены? Допустим, D.

В каждый конкретный момент может быть выключено N серверов из N . Задача сервера — при подъеме начать коннектится к серверам из своего списка (т.е. сохраняется некий архив серверов, доступных на момент последнего включения) и синхронизировать данные о серверах. Результатом всей этой работы должны быть практические идентичные списки у всех серверов в сети. В принципе, достаточно поддерживать их 90%-ную актуальность. Я подумываю, что вариант, предложенный PK Sly, может вполне пригодиться для этих целей — сервер, подключаемый в сеть, будет сам сообщать о себе всем серверам в сети, синхронизируя списки. Рано или поздно синхронизация пройдет полный круг (во всяком случае — должна по прикидкам). А если при получении нового сервера еще сделать возврат назад (т.е. разослать его адрес серверам, с которыми я уже синхронизировался), то, думаю, overhead будет не таким большим при выполнении условия поддержания актуальности списков.

К>Значит, если мы построим граф с N вершинами, каждая из которых смежна с D+1 другими, то пакет будет гарантированно разослан всем.
К>В худшем случае будет отправлено
К>1 + 1*(D+1) + (D+1)*L,
К>где L — диаметр графа. L ~ N/D, тут надо подумать над точным значением.

К>Пример: D=1, делаем кольцо. k-й сервер общается с k-1 и k+1.
К>D=2. k общается с k-1, k+1 и k+(N/2)
К>D=N-1. Каждый общается с каждым.

Спасибо, подумаю над этим.