Как отправить сообщение о не доступности сервера, из распределенной сети?

Зависит от того как сервер падает и как от того падает ли он один, пачкой или вообще все, ну и от того как вы понимаете, что сервер упал.
Для задачи в вакууме (той что в вопросе) можно сделать скрипт который при старте будет рассылать остальным серверам, что то вроде: "Кто из нас шлёт сообщения, если никто то буду я" и гонять его по крону с нужным интервалом. Таким образом по умолчанию будет рассылать тот сервер на котором первым запустился скрипт, а если он упадёт то первый из тех кто заметил.