Простой подход, если у вас есть выделенный лидер и по графу распространяется одна волна в каждый момент времени.
Лидер опрашивает остальные сервера по очереди (включая себя), и справшивает их, есть ли у них еще непокрашенные вершины. Если есть, инструктирует их запустить волну. Когда волна закончится, справшивает опять. Когда сервер говорит, что больше непокрашенных вершин нет - лидер переходит к следующему серверу.
Когда сервер запускает волну - он обходит все вершины у себя, если встречает призрачное ребро, то посылает сообщение другому серверу запустить обход у себя с присоеденненной вершины.
Чтобы отследить конец волны, перед запуском обхода в другом сервере, каждый сервер отслывает лидеру сообщение, что вот тот сервер теперь будет работать. Когда волна в каком-то сервере заканчивается, он присылает лидеру сообщение, что все закончилось. Лидер поддерживает счетчик - сколько еще серверов работает. Когда счетчик достигает 0, надо еще подождать немного (скажем, пол секунды), на случай реордеринга сообщений. Если в течении этой пол секунды никаких сообщений не пришло, можно запускать новую волну.
Более сложный вариант - когда у вас сразу запускаются все волны. Опять же, без лидера совсем сложно будет.
Тут, наверно стоит сначала в каждом отдельном параграфе найти все компоненты связности отдельно. Это будут промежуточные варианты.
Потом каждый сервер по призрачным ребрам отсылает сообщение, какой номер имеет торчащая наружу компонента. Номера должны быть глобально уникальные. Например, можно в старших битах хранить номер сервера, а в младших локально уникальный номер.
Когда сервер получает сообщение о номере по призначному ребру, если этот номер меньше текущего у компоненты, она перекрашивается. И сообщение рассылается по всем остальным призрачным ребрам, торчащим из этой компоненты. Рано или поздно, все вершины одной компоненты по всем серверам будут помечены минимальным номером.
Чтобы определить, что все закончилось, можно разбить процесс на фазы. В первой фазе все рассылают свои номера. Во второй фазе только те, у кого номера обновились. И т.д. Фаза на сервере начинается после сообщения от лидера. Каждый сервер отправляет на лидер сообщение, когда он закончил рассылать свои номера и были ли там вообще обновления. Сообщения надо делать по tcp с подтверждением. Когда лидер заметит, что никто никаких сообщений больше не рассылал в предыдущей фазе - все сошлось.
