Title :
A message-optimal protocol for global surveys in faulty networks
Author :
Luo, Kenneth C -K ; Chow, Yuan-Chieh
Author_Institution :
Dept. of Comput. & Inf. Sci., Florida Univ., FL, USA
Abstract :
The problem of conducting a global survey in faulty networks is studied. The global survey problem (GSP) can be considered as an extension of that of network broadcasting. It is shown that the time complexity lower bound for the GSP is Ω(|V|) and the message complexity is Ωmin(|V|,k)|V where k is the number of links failed. While there is a straightforward protocol to achieve the time complexity lower bounds, the design of message-optimal protocols is rather complex. This work provides such a protocol
Keywords :
computational complexity; failure analysis; protocols; telecommunication networks; trees (mathematics); computational complexity; faulty networks; global surveys; high-tree algorithm; low-tree algorithm; message-optimal protocol; Broadcasting; Computer network reliability; Computer networks; Delay effects; Distributed computing; Hardware; Intelligent networks; Nominations and elections; Propagation delay; Protocols;
Conference_Titel :
INFOCOM '91. Proceedings. Tenth Annual Joint Conference of the IEEE Computer and Communications Societies. Networking in the 90s., IEEE
Conference_Location :
Bal Harbour, FL
Print_ISBN :
0-87942-694-2
DOI :
10.1109/INFCOM.1991.147549
