292
правки
Изменения
Новая страница: «Категория: Параллельное программирование {{Определение |definition= '''Диффундирующее вычис…»
[[Категория: Параллельное программирование]]
{{Определение
|definition=
'''Диффундирующее вычисление''' — это вычисление, которое происходит следующим образом:
* Каждый процесс бывает либо ''активным'', либо ''пассивным''
* Если процесс получает сообщение, он становится активным
* Только активный процесс может посылать сообщения
* Активный процесс может в любой момент по своему желанию стать пассивным
* Исходно есть ровно один активный процесс — инициатор
}}
Пример: распределённый алгоритм Дейкстры для поиска кратчайшего пути. Каждой вершине соответствует процесс, он рассылает соседям (с которыми связан ребром) улучшенные расстояния до них.
{{Определение
|definition=
Диффундирующее вычисление '''остановилось''', если все процессы пассивные и нет сообщений в пути (потому что они могут кого-то активизировать).
}}
Замечание: это стабильный предикат.
{{Определение
|definition=
'''Проблема останова диффундирующего вычисления''': как инициатор узнает о том, что вычисление остановилось?
}}
{{Определение
|definition=
'''Диффундирующее вычисление''' — это вычисление, которое происходит следующим образом:
* Каждый процесс бывает либо ''активным'', либо ''пассивным''
* Если процесс получает сообщение, он становится активным
* Только активный процесс может посылать сообщения
* Активный процесс может в любой момент по своему желанию стать пассивным
* Исходно есть ровно один активный процесс — инициатор
}}
Пример: распределённый алгоритм Дейкстры для поиска кратчайшего пути. Каждой вершине соответствует процесс, он рассылает соседям (с которыми связан ребром) улучшенные расстояния до них.
{{Определение
|definition=
Диффундирующее вычисление '''остановилось''', если все процессы пассивные и нет сообщений в пути (потому что они могут кого-то активизировать).
}}
Замечание: это стабильный предикат.
{{Определение
|definition=
'''Проблема останова диффундирующего вычисления''': как инициатор узнает о том, что вычисление остановилось?
}}
