Constellation resource discovery model is a novel model for discovering the dynamic resources in Grid. In constellation model, we propose a new Scalable Multi-tape Universal Turing machine (SMUTM) to present the processes of simultaneous discovery tasks on the constellation nodes, and formally describe the usability of the Grid resource based on the SMUTM. In this research, we design an algorithm used in the constellation resource discovery, which guarantees overlaying all the nodes in Grid and optimizes the network cost. Preliminary simulation shows that this algorithm complexity is linear; the average response time can be reduced by 12%. Constellation model ensures the QoS of the resource discovery in the scalable and dynamic Grid environment.