http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=94.142.26.31&*Викиконспекты - Вклад участника [ru]2026-05-04T05:17:58ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A6%D0%B5%D0%BD%D1%82%D1%80%D0%B0%D0%BB%D0%B8%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B4%D0%BB%D1%8F_WCP&diff=64543Централизованный алгоритм для WCP2018-03-21T21:37:34Z<p>94.142.26.31: </p>
<hr />
<div>[[Категория: Параллельное программирование]]<br />
'''Централизованный алгоритм для WCP''' – алгоритм для поиска наименьшего (проще говоря, самого левого) [[Срез, согласованный срез|согласованного среза]] в котором выполняется [[Слабый конъюнктивный предикат (WCP)|слабый конъюнктивный предикат]].<br />
<br />
В централизованном алгоритме используются [[Векторные часы|векторные часы]]. Срез задается набором векторных часов для всех процессов.<br />
<br />
Суть алгоритма:<br />
* Есть один процесс-координатор, ответственный за поиск согласованного среза;<br />
* Остальные процессы обычные, их задача проверять свои локальные предикаты;<br />
* Всякий раз, когда впервые с момента последнего отправленного сообщения локальный предикат становится true, оповещаем об этом координатора, указывая свое векторное время;<br />
* Координатор поддерживает в памяти срез-кандидат и очередь необработанных сообщений от каждого процесса;<br />
* Срез-кандидат согласован тогда и только тогда, когда все соответствующие вектора попарно несравнимы;<br />
* Координатор хранит вектора среза-кандидата и флажок для каждой его компоненты: красный – этот элемент не может быть частью согласованного среза, зеленый – может;<br />
* Начальное состояние – все по нулям, красные;<br />
* Обрабатываем приходящие сообщения только от красных процессов, сообщения от зеленых ставим в очередь:<br />
** Сравниваем пришедший вектор попарно с другими процессами, если новый вектор больше, то делаем меньший процесс красным;<br />
** После обработки сообщения делаем процесс зеленым.<br />
* Если все зеленое, то мы нашли согласованный срез.</div>94.142.26.31