Введение в распределенные

Передача маркера запроса. Философ u отправляет соседнему философу v соответствующий маркер запроса, если 1) u владеет маркером, 2) у философа u отсутствует общая с v вилка и 3) u голоден.

Передача вилки. Философ u пересылает философу v общую с ним вилку, если 1) у u вместе с этой вилкой находится соответствующий ей маркер запроса, 2) вилка – "грязная" и 3) u не принимает пищу. При передаче вилки она "очищается".

Переход из голодного состояния в состояние приема пищи. Голодный философ u может начать принимать пищу только тогда, когда u владеет всеми вилками от всех своих соседей, и для любого его соседа v верно, что общая с ним вилка – "чистая", либо у u не

находится маркера запроса от v. Когда философ u переходит в состояние приема пищи, все находящиеся у него вилки становятся "грязными".
Начальное состояние распределенной системы. Представленное выше решение задачи обедающих философов опирается на следующие инварианты:

• 
  граф H остается ациклическим;
  
• 
  принимающий пищу философ владеет всеми вилками со всех инцидентных ему ребер;
  
• 
  "чистыми" вилками владеют только голодные философы;
  
• 
  философ владеет вилкой и соответствующим ей маркером запроса только тогда, когда его сосед голоден.
  

Поэтому начальное состояние распределенной системы также должно обеспечивать выполнение перечисленных утверждений. А именно, изначально вилки должны быть распределены среди философов таким образом, чтобы в H не было циклов. Кроме того, если предположить, что в начальном состоянии все философы находятся в размышлениях, то все вилки должны быть "грязными", и ни у одного из философов одновременно с вилкой не должен находиться соответствующий ей маркер запроса.
Теперь продемонстрируем, что представленное решение задачи обедающих философов обладает требуемыми свойствами.

1.