Abstract: Grid provides large numbers, various types of dynamic services in a distributed environment. A grid service location mechanism is described to improve service location of diverse properties. According to the Small-World theory, VO（virtual organization） concept is used to divide logic grid services into different organizations based on grid user’s requirement and sharing purpose of services. An XML document named VODL（virtual organization description language） is proposed to describe VO’s property, which enables the grid users to access the information of grid services and virtual organizations. A message dissemination algorithm for the grid model is presented. Finally, a performance evaluation of the algorithm is analyzed theoretically, which shows its characteristics of the Small-World network.