Алгоритмы, дискретная математика и пр.'s Journal (original) (raw)

2:08p

Доставка сообщений Есть группа людей неизвестной величины.
Любой человек может передавать любым другим сообщение, как свое, так и повторять чужое. Но не может передавать сообщение всем сразу, только по одному и только конечному числу, меньшему чем общее количество людей в группе.
Фактически это чат, только без центрального сервера. Либо другой вариант: постоянно растущий файл в системе типа битторрент, но который необходимо раздавать всем без исключения.
Каким образом можно решить такую задачу?
Небольшое количество повторных сообщений, которые придут одному лицу не страшно. Однако рассылать по системе "каждый-каждому" нельзя, не хватит ресурсов.
Есть немного другой подход: опрашивать других на предмет наличия новых сообщений, следовательно придется хранить какой-то объем сообщений. Здесь есть плюс, т.к. гарантия доставки выше, но есть и минус: два сообщения - запрос и ответ, вместо одного, когда просто идет рассылка без запроса, который должен обходится "дешевле".
Наверное нужно построить какое-то хитрое дерево, но есть сложность: новые люди в группе то появляются, то исчезают. К тому же хочется сделать более менее равномерную нагрузку.