In this paper, the problem of the distributed network survivability is investigated. A distributed system is modeled by a finite connected undirected graph whose nodes are divided into two types: hosts and switches. Hosts perform computational functions, while switches are utilized for providing the message delivery between hosts. The system survivability is considered as the system ability to perform the main functions of message transmission after graph edges’ failures. The solution for the system survivability is provided by duplicating the paths for message transmitting. The main condition for the correct solution is the absence of message looping in the network for any set of selected paths. The four-path theorem is proved for the case of two recipient hosts: if for each recipient host there are two paths from the sending host and the edge sets traversed by these paths are disjoint, then there is no message looping for this set of the paths.
Исследуется проблема живучести распределенных сетей. Распределенная система моделируется конечным связным неориентированным графом, вершины которого делятся на два типа: хосты и коммутаторы. Хосты выполняют вычислительные функции, а коммутаторы обеспечивают доставку сообщений между хостами. Под живучестью системы понимается ее способность выполнять свои основные функции по передаче сообщений после выхода из строя некоторых ребер графа. Решение проблемы живучести системы обеспечивается дублированием путей, используемых для передачи сообщений. Основным условием корректного решения является отсутствие зацикливания сообщений в сети при выбранных основных и дублирующих путях. Доказывается теорема о четырех путях для случая одного хоста-отправителя и двух хостов-получателей: если для каждого из двух хостов-получателей существуют два непересекающихся по ребрам пути из хоста-отправителя в этот хост-получатель, то можно выбрать эти четыре пути такими, что зацикливания сообщений не возникнет.