RippleLog: A Path Search Algorithm for a Distributed Query Processing

Distributed query processing (DQP) requires data or decomposed sub-queries be routed to different destination nodes for execution, thus a path search algorithm is needed to find best paths for data/query transmissions. When a node doesn´t know how to route a data/query to a specified destination node, the path search algorithm on the node has to initiate a message passing procedure around its neighbors to find the best path to the destination. To accomplish the path search with low message passing traffic for distributed query processing, the paper propose a distinctive path search algorithm, RippleLog, which is composed of the following two mechanisms: 1)the incremental message passing mechanism, which limits the number of nodes involved for the path search so as to reduce the message passing traffic; 2)the logging mechanism, which maintains a message-log on each node for the best path evaluation and further reduce the message passing traffic.