Представлен анализ объема передаваемых сообщений в двух различных реализациях параллельного алгоритма поиска в ширину на графе. Первая из реализаций представляет собой поиск в ширину с точечными обменами данных. Вторая реализация - поиск в ширину с “обратным ” направлением обхода и синхронизацией данных посредством битовой маски. Показано, что использование первой реализации обладает большими накладными расходами на промежуточных итерациях, в то время как вторая реализация демонстрирует умеренный объем накладных расходов на протяжении всего времени исполнения алгоритма.