Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Алгоритм Финна





Алгоритм Финна – еще один волновой алгоритм, который можно использовать в ориентированных сетях произвольной топологии. Он не требует того, чтобы диаметр сети был известен заранее, но подразумевает наличие уникальных идентификаторов процессов. В сообщениях передаются множества идентификаторов процессов, что приводит к довольно высокой битовой сложности алгоритма.

Процесс сайта s содержит два множества идентификаторов процессов, Inc(s) и NInc(s). Неформально говоря, Inc(s) – это множество процессов u таких, что событие в u предшествует последнему произошедшему событию в s, а NInc(s) – множество процессов u таких, что для всех соседей r процесса u событие в r предшествует последнему произошедшему событию в s. Эта зависимость поддерживается следующим образом.

Изначально Inc(s) = { s }, а NInc(s) = Æ. Каждый раз, когда одно из множеств пополняется, процесс s посылает сообщение, включая в него Inc(s) и NInc(s). Когда s получает сообщение, включающее множества Inc(s) и NInc(s), полученные идентификаторы включаются в версии этих множеств в процессе s. Когда s получит сообщения от всех соседей по входу, s включается в NInc(s). Когда два множества становятся равны, s выполняет процедуру return (OK). Из неформального смысла двух множеств следует, что для каждого процесса u такого, что событие в u предшествует некоторому событию e, выполняется следующее: для каждого соседа r процесса u событие в r также предшествует событию e.

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

Date: 2015-09-18; view: 811; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию