Синхронизаторы и остовы: различия между версиями

Рассмотрим коммуникационную сеть, моделируемую неориентированным взвешенным графом G = (V, E) с n вершинами, где n – целое положительное число. Каждая вершина G содержит процессор неограниченной вычислительной мощности; вершины имеют уникальные идентификационные номера и общаются друг с другом посредством дуг из G, пересылая друг другу сообщения размера O(log n).

В случае ''синхронной'' организации коммуникация осуществляется в виде дискретных ''раундов'', и сообщение, отправленное в начале раунда R, прибывает в точку назначения до его окончания. В случае ''асинхронной'' организации каждая вершина поддерживает собственный тактовый синхронизатор, причем у разных вершин они могут не совпадать. Предполагается, что каждое отправленное сообщение (в случае синхронной организации) прибывает в точку назначения в течение определенного временного интервала <math>\tau \;</math> после отправки, однако значение <math>\tau \;</math> процессорам неизвестно.