Задачка о распределённом поиске максимума

Есть N вычислителей. От каждого вычислителя идут каналы связи к соседним вычислителям. Количество вычислителей и топология сети неизвестны. Но известно что граф связный. Вычислители работают по тактам. За один такт вычислитель принимает сообщения от всех своих соседей которые они ему отправили на предыдущем такте, производит некоторые вычисления и может отправить своим соседям сообщения, которые они получат на следующем такте. Размер сообщения фиксированный. У каждого вычислителя в 0й такт времени есть некоторое число Xi и они хотят вычислить максимум. Алгорит считает завершённым когда обладатель максимума узнает о том, что все вычислители знают максимум. Пока считаем что все числа X различны. Потом можно будет порешать задачку когда некоторые числа Xi совпадают, но максимум только у одного вычислителя. Или даже когда максимум может быть у нескольких вычислителей, правда мне кажется что в этом случае решение задачки не гарантируется.

 

Возможен ли такой вариант: в собщении есть битовое поле, число бит = числу вычислителей. Если на вычислитель приходит число, большее, чем в нем хранится, то установить бит соответствующего вычислителя в 1. Когда все биты установятся - максимум найден.

 

KeSqueer
Невозможен, размер сообщения фиксированный, а сколько вычислителей неизвестно.

Кстати определить какому вычислителю какой бит соответствует они тоже не могут, единственное отличие между вычислителями это как раз число X (есть еще конечно связи с соседями, но для решения этой задачи топология сети несущественна).

 

самое простое (что сразу приходит в голову), так это вот что:
такт0: отправить свое число соседним вычислителям
такт1:
принять от соседей их числа и сравнить со своим; запомнить наибольшее и отправить соседям
...
тактN: независимо от топологии, все вычислители имеют максимальное число.

 

Nero_n
Только как они определят что все из них уже знают максимальное число?

 

Black_mirror
Топология, блин... Возьмем, к примеру, два одинаковых связных графа и соединим их одним ребром. Тогда за некоторое количество тактов эти два графа могут выяснить значение своего "локального" максимума (т.е. максимума по значению "своих" чисел), а затем обменяться значениями этих максимумов по одиночному соединяющему их ребру и получить глобальный максимум на основе этих двух значений.

 

crypto
Алгоритм "когда-то все об этом узнают" не годится, нужно чтобы хотя бы один вычислитель определил что максимум уже знают все.

 

Black_mirror
"Момент истины" наступит, когда после определенного количества тактов найденное вычислителем значение не будет увеличиваться. Это число тактов связано с максимальным (по всем парам различных вершин графа) значением d(u,v), где d - минимальное расстояние между вершиами u и v (как-то эта характеристика графа называется, не помню). Т.е. грубо говоря, когда кажое исходное число будет обработано каждым вычислителем.

 

crypto
Эта характеристика диаметром графа называется, но он нам не известен, у нас может быть цепочка, дерево или вообще полносвязный граф, вот всех этих случаях алгорит должен опреределить момент когда максимум знают все. Но возможно, что это будет определено позже чем все узнают максимум.

 

Black_mirror
Мне кажется, надо хотя бы с деревьев начать, все-таки самые простые связные графы.

 

Black_mirror
Кстати, поскольку на сообщения вроде никаких ограничений не накладывалось, то при каждой пересылке можно передавать номера узлов, от которых были получены сообщения и результат вычисления. При получении сообщения вычислитель анализирует список узлов и при необходимости выполняет вычисления и добавляет новый узел в список.
При формировании хотя бы на одном вычислителе полного списка узлов (думаю, что несмотря ни на какие ограничения со стороны ТС, количество узлов сети известно ) вычисления заканчиваются.
Оффтоп
В качестве пояснения к количеству узлов.
Первая фраза:

Третья фраза:

 

http://en.wikipedia.org/wiki/Leader_election

 

Black_mirror
врятли можно придумать что-то лучшее, чем разбивка на подмножества, нахождение локальных экстремумов и затем вычисление глобального. хотя подобная система может работать медленей одиночной машины, ибо есть накладные расходы распределения задания. короче, выигрыш будет только для больших массивов.

 

crypto
Номеров у узлов нет, количество узлов неизвестно.

[add]Их ровно N, но N неизвестно [/add]

Stiver
Насколько я понял, там рассматриваются асинхронные алгоритмы, а у нас тут всё работает синхронно.

 

Хочется спросить, а почему номеров нет? Так не бывает.

 

Black_mirror

То есть стандартные алгоритмы не будут работать в синхронном случае? Интересно.. надо проверить.

 

crypto
Можно числа считать номерами, по крайней мере в первом варианте, когда все числа различны. Но это не значит что они имеют значения от 1 до N. Чему равно N мы вообще не знаем.

Stiver
Думаю что будут, только что-то мне подсказывает что они могут быть менее эффективны. Для первого варианта задачи есть решение за время не превышающее удвоенного диаметра графа.

 

Black_mirror
а, так ещё и N неизвестно...

если бы можно было сначала пересчитаться)...

 

такт0: каждый узел отправляет соседям свое число.

тактХ: максимум из всех доступных (присланные+свое) значений запоминаем (но свое число сохраняем). посылаем максимум всем узлам, кроме тех, от которых пришел максимум (или всем узлам, если текущим максимумом является наше число). НО: если на предыдущем такте от _всех_ соседей пришло одинаковое число, которое больше нашего, то отправляем максимум _всем_ соседям.

(не вместилось)->

 

обладатель абсолютного максимума узнает, что все узлы узнали max, когда к нему от _всех_ соседей прийдет его же собственное число.