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

В случае синхронной организации коммуникация осуществляется в виде дискретных раундов, и сообщение, отправленное в начале раунда R, прибывает в точку назначения до его окончания. В случае асинхронной организации каждая вершина поддерживает собственный тактовый синхронизатор, причем у разных вершин они могут не совпадать. Предполагается, что каждое отправленное сообщение (в случае синхронной организации) прибывает в точку назначения в течение определенного временного интервала x после отправки, однако значение т процессорам неизвестно.

В общем случае оказывается намного проще разрабатывать алгоритмы, рассчитанные на синхронную организацию (называемые синхронными алгоритмами), чем на асинхронную (соответственно, асинхронные). Авербух [ ] инициировал исследование техник моделирования, которые переводили бы синхронные алгоритмы в асинхронные. Такие техники моделирования называются синхронизаторами.

При разработке первых синхронизаторов Авербух предложил определенное разбиение графа, представляющее интерес само по себе. В частности, Пелег и Шеффер [8] заметили, что это разбиение порождает подграф с определенными любопытными свойствами. Такой подграф они назвали остовом графа. Формально для целого положительного параметра k k-остовом графа G = (V, E) является подграф G0 = (V, H), H С E, такой, что для каждого ребра e = (v, u) 2 E расстояние между вершинами v и u в H, distG0(v, u), не превышает k.