Adaptive breadth-first search protocols

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We present adaptive protocols for the problem of breadth-first search in a distributed system. An adaptive protocol can change its behavior in response to changes in the network environment, which might be useful to satisfy certain performance requirements and to enhance the life cycle of a software system. We obtain an adaptive protocol by combining two existing breadth-first search protocols, A and B. A performs better than B if network topology is sparse or if the actual message delays on different links during the execution of the protocol are the same. Otherwise, it is more costly to operate than B. Protocol Comp(A,B), which we obtain by composing A and B, performs well under a variety of network conditions. It behaves like A whenever conditions are favorable and like B otherwise. Its message complexity on any topology is the minimum of the message complexities of A and B on that topology. Using the same technique, we obtain another adaptive protocol by combining A with another protocol C. The performance characteristics of this protocol are similar to those of Comp(A,B). Protocols obtained using our technique exhibit an additional property of local adaptivity i.e., the protocols adapt themselves locally to changes in the network.

Original languageEnglish (US)
Title of host publicationConference Proceedings - International Phoenix Conference on Computers and Communications
PublisherIEEE Computer Society
Pages261-267
Number of pages7
ISBN (Print)0780318153
StatePublished - Jan 1 1994
Externally publishedYes
EventProceedings of the 1994 IEEE 13th Annual International Phoenix Conference and Communications - Phoenix, AZ, USA
Duration: Apr 12 1994Apr 15 1994

Publication series

NameConference Proceedings - International Phoenix Conference on Computers and Communications
ISSN (Print)0896-582X

Other

OtherProceedings of the 1994 IEEE 13th Annual International Phoenix Conference and Communications
CityPhoenix, AZ, USA
Period4/12/944/15/94

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Adaptive breadth-first search protocols'. Together they form a unique fingerprint.

  • Cite this

    Singh, G. (1994). Adaptive breadth-first search protocols. In Conference Proceedings - International Phoenix Conference on Computers and Communications (pp. 261-267). (Conference Proceedings - International Phoenix Conference on Computers and Communications). IEEE Computer Society.