A Grid Theoretical Model And Its Application

The explosion of computer and network technology advancements, together with the emergence and far-flung application of Internet, created an explosion in the development and research of commercial and scientific applications under network environment. Grid technology aims at meeting this requirement. A grid system connects/integrates together geographically distributed heterogeneous high-performance computers, data servers, storage systems, visualization and virtual reality systems with high speed networks to solve momentous application problems that can not solved by present methods and realize resource share.Nowadays, the grid research is focused on the construction of grid systems and the development of grid softwares and applications. The problem of grid theoretical model is seldom mentioned. This thesis explored several key theoretical problems of grid systems in the development and research of NHPCE and Vega Grid. The main innovations are the followings: â‘ Presenting a grid theoretical model named GAM based on the asynchronous I/O automata theory and formalizing grid system with this model, â‘¡Studying some essential grid algorithms and properties of grid systems with GAM, â‘£Presenting a grid access control model GACM.We bring forward a grid theoretical model named GAM based on asynchronous I/O automata theory after we have analyzed present grid systems, such as Globus, Legion, and our Vega Grid. We formalized the grid node and the communication subsystem which are two key components of grid system. This model could not only be used to research and analyse present grid systems, but also to design new grid systems.We formalized three kinds of communication subsystems of grid: point-to-point, broadcast and multicast. We also studied the properties of these subsystems. Though we suppose all these communication channels are reliable, the formalization of fault-tolerant channels, such as TCP/IP, UDP channels, with our model is viable.After we have presented GAM, we studied some essential algorithms and properties of grid systems. Among the most fundamental tasks to be performed in a grid environment are the construction of a spanning tree for the grid or task rooted at a given source node and the use of such a tree for performing broadcast and convergecast communication. We presented three kinds of breadth-first spanning tree algorithms: GridBFS, LayerBFS and MiddleBFS, and proved all these algorithms will eventually produce a spanning tree which includes all the nodes of the grid. We also formalized the grid shortest path algorithm, and proved this algorithm will eventually produce a shortest path for each non-source node. The time and communication complexities of these algorithms are analyzed. And these algorithems are applicable to grid monitoring and grid deadlock detection.