В настоящее время я борюсь со следующим упражнением: существует заданный, неориентированный и связанный случайный граф узлов.Каждый узел представляет собственный процесс и знает свои соседние процессы (узлы).Каждый узел может общаться только со своими соседними процессами.Первоначально каждый узел имеет случайное целочисленное значение.Цель состоит в том, чтобы все узлы вычисляли среднее значение этого целого числа.Для этого мне необходимо реализовать следующий алгоритм:
Два случайных узла (N (1) и N (x)) инициируют этот распределенный алгоритм.Они выбирают до двух соседних узлов (N (2) и N (y)) и отправляют им значение их переменной.
Принимающий узел N (2) вычисляет среднее значениепринятой и его собственной переменной.
Принимающий узел N (2) сохраняет рассчитанное значение в качестве своего текущего значения и отправляет его инициатору N (1).
N (1) получает вычисленное значение и сохраняет его в качестве текущего значения.
N (1) и N (2) теперь содержат одно и то же целое числозначение.
N (1) инициирует следующий расчет с помощью N (x) ...
N (2) выбирает до двухдополнительные соседние узлы, и процесс начинается снова.
Узел завершается, если он участвовал в указанном количестве вычислений.
Я реализовал это до сих пор в JAVA наоснованный на событиях подход: каждое входящее коммуникационное сообщение будет добавлено в конец очереди событий, чтобы гарантировать, что узел не выполняет два вычисленияв то же время.
Поэтому шаги всегда должны выполняться, как указано выше.
Я использую следующие события:
"REQUEST_CALCULATION": Узел 1запрашивает расчет в Узле 2, отправляя его текущее значение.
"ACK_CALCULATION": Узел 2 выполнил вычисление и отправляет новое значение обратно Узлу 1.
Пока что приложение распределений работает нормально, но процессы, работающие в тупики на регулярной основе: из-за последовательной обработки событий события в очереди не могут быть выполнены, так как сосед блокировки неотправив свой результат.
Я пытался решить эту проблему по-разному:
Если узел ждал x секунд результата, я предполагаю тупик, отмените текущий расчети перейдите к следующему событию в очереди.Этот обходной путь делает свое дело, но распределенное вычисление завершается довольно быстро: все узлы переходят в режим ожидания, поскольку многие вычисления (и впоследствии пересылка двум другим соседям после успешного вычисления) теряются.
Как и выше, но вместо полной отмены события я заново инициирую его и помещаю в конец очереди.Обычно это заканчивается бесконечным циклом, где одни и те же сообщения между множеством узлов постоянно повторяются.
Чтобы избежать 2), я добавил случайную задержку на потребление событий в очереди,Хотя это уменьшает количество взаимоблокировок, этот взлом не может быть окончательным решением.
Я полагаю, что взаимоблокировки являются лишь побочным эффектом сбоя в базовой концепции моего приложения.Поэтому я хотел бы попросить вас дать некоторые рекомендации о том, как запустить этот процесс распределенного вычисления, также независимо от моей ранее описанной реализации.
Заранее благодарен за вашу помощь, отзывы и отзывы.