GRR ensures that successive work request are distributed evenly across processors. Difficulty is in centralized bottleneck processor . Analysis of Parallel Search Assume a parameter which states that after work requests, each processor receives at least one work request. The communication overhead for parallel DFS is where W is amount of search work, is cost of communication for one piece of work. Imagine the p processors to be connected in a ring, .
Processor initiates a token when it becomes idle, sends to .
At any stage, token is held in processor until that processor completes. Algorithm completes when receives token provided no work placed on idle processors. When processor becomes, it initiates termination detetcion by making itself white and sending a white token to . If processor has the token and is idle, then it passes the token to . If is black, then color of token sent is black.