Для синхронных распределенных алгоритмов обычно рассматриваются два типа сложности:
- временная сложность (time complexity)
- коммуникационная сложность (communication complexity)
Временная сложность синхронной системы измеряется количество проходов пока не будут получены все требуемые выходные данные или пока все процессы не остановятся.
Коммуникационная сложность обычно измеряется общим количеством отправленных непустых сообщений. Иногда также берется в расчет количество битов в сообщениях.
Временная оценка более важна на практике не только для синхронных распределенных алгоритмов, но и вообще для всех распределенных алгоритмов. Коммуникационная сложность представляется существенной только в случаях, когда она образует достаточную перегрузку чтобы замедлить обработку. Такое предположение позволяет игнорировать коммуникационную сложность и рассматривать только временную сложность. Однако воздействие коммуникационной нагрузки на временную сложность это не просто функция какого-нибудь конкретного распределенного алгоритма. В обычной сети много распределенных алгоритмов работают одновременно и совместно используют одну и ту же полосу пропускания. Нагрузка конкретного сообщения, добавленная на связь любым одним алгоритмом добавляется к полной нагрузке сообщений на этой связи и таким образом способствует перегрузке, которая замечается всеми алгоритмами. Так как трудно определить степень влияния сообщений какого-нибудь алгоритма на временную производительность других алгоритмов, мы будем использовать простой анализ (и попытаемся минимизировать) количества сообщений генерируемых каждым конкретным алгоритмом.
