Неограниченный недетерминизм
-
Определение и роль неограниченного недетерминизма
- Неограниченный недетерминизм — свойство параллелизма, позволяющее задержку в обслуживании запросов.
- Гарантирует обработку запроса в конечном итоге, несмотря на споры за ресурсы.
-
Связь с справедливостью
- Все пути вычислений должны быть справедливыми, т.е. выполнять все возможные переходы из состояния.
- Требует, чтобы машина обслуживала запрос, если это возможно.
- Отличается от локальной справедливости подбрасывания монеты.
-
Пример использования неограниченного недетерминизма
- Уильям Д. Клингер использовал неограниченный недетерминизм для объединения строк.
- Доказательство Клингера привело к противоречию, что указывает на невозможность реализации неограниченного недетерминизма.
-
Ограничения и споры о неограниченном недетерминизме
- Эдсгер Дейкстра и Тони Хоар утверждали, что реализация систем с неограниченным недетерминизмом невозможна.
- Гордон Плоткин доказал, что недетерминированные автоматы имеют ограниченный недетерминизм.
- Уильям Клингер и Карл Хьюитт разработали модель актора с неограниченным недетерминизмом, но ограниченную рекурсивными функциями.
- Хьюитт использовал неограниченный недетерминизм в арбитраже для решения проблемы асинхронности в компьютерных часах.
-
Анализ справедливости и рекомендации
- Хьюитт утверждал, что справедливость в моделях вычислений отличается от неопределенности порядка прибытия.
- Дана Скотт обсуждает денотационную семантику и её роль в информатике.