February 11, 2008 3:20pm Domenico Talia

Grids are moving from a computation and data management platform to a pervasive, worldwide information and knowledge management infrastructure. This trend needs new models and technologies for enabling Grid computing to support fine grained Grid nodes and resources that can be connected in a simple, dynamic, and self-organizing way. Self-organizing knowledge grids can help to build up a pervasive infrastructure for managing and diffuse information and knowledge.Full Article...

Domenico Talia
University of Calabria, talia@deis.unical.it

Grids are moving from a computation and data management platform to a pervasive, worldwide information and knowledge management infrastructure¹. This trend needs new models and technologies for enabling Grid computing to support fine grained Grid nodes and resources that can be connected in a simple, dynamic, and self-organizing way. Self-organizing knowledge grids can help to build up a pervasive infrastructure for managing and diffuse information and knowledge.

Principles
A self-organizing knowledge grid is a system of irregularly placed, asynchronous, locally or remotely interacting knowledge processing elements. We can model this organism as a collection of "computational particles" sprinkled irregularly on a surface or mixed throughout a volume. The particles are possibly faulty, sensitive to the environment, and may take autonomous actions. In general, individual grid particles may be mobile. Each particle has large or modest computing power and generally a limited amount of memory although in some cases they manage large storage. The particles are not necessarily synchronized, although they compute locally or in cooperation with other particles and interact each other according different patterns.

Self-organizing knowledge grids do not need to have definite form or distinct shape; like self-organizing clouds of insects they can act as an aggregate of formless particles that constitute a shapeless mass of "computing protoplasm". The particles are all programmed to perform some tasks or provide some service and to interact with other particles or the external environment. Each one has means for storing local state. Each grid particle can communicate with nearby neighbors or remote elements. In self-organizing knowledge grids of small particles, they may communicate via wireless media and wired interconnections. For our purposes here, we can assume there is some interaction radius R that is large compared to the size of single particles and small compared to the size of an entire area or volume, and that two particles are considered to be neighbors if they are within distance R. The radius represents the particle's horizon that defines the maximum distance for discovering and interacting with other grid particles.

In self-organizing knowledge grids the number of particles can be very large. Thus, the entire self-organizing knowledge medium can be regarded as a large-scale knowledge Grid system that may change its form/configuration depending from particle behavior and from the external environment. Previous researches in Grid computing, peer-to-peer networks, global computing, Web services, massively parallel computing, knowledge discovery, pervasive computing², artificial intelligence, and self-organizing systems are sources of ideas for dealing with self-organizing knowledge grids. A self-organizing knowledge grid is a greater challenge than single systems mentioned above, however, because its mechanisms embody features and functionalities of all those systems. For example, it is must exploit self-organization, it must be independent of configuration and reliability of the individual particles, it exploits "smart dust" technologies³, it must open to new particles or new clusters or aggregates of particles, and adaptive to the problems to be solved or the user requirements.

Towards a Programming Model
Today Grids differ significantly from self-organizing knowledge grids in terms of application and machines granularity, connectivity, security, mobility, etc. These differences imply the necessity to devise new tools and new models for deployment and application development on such class of systems^4,5. In other words, mechanisms for setting up and programming self-organizing knowledge grids are needed. Programming those systems must be done either by programming a single particle or an aggregate of grid particles. This new paradigm could stimulate advancements also in the area of service computing towards the definition of more flexible and light service models.

Each particle can query and potentially modify its state and the state of another particle depending on the particle-to-particle interaction and on the state of the neighbor particles. Self-organization is the basic paradigm for particle programming and evolution. Since a limited or a massive amount of particles can compose a self-organizing knowledge grid, a programming model for such a kind of system must be able to manage small sized and very large sized self-organizing knowledge grids. An appropriate programming model for self-organizing knowledge grids comes from self-organizing programming models and from cellular programming languages that include constructs to define cell or particle behavior and particle-to-particle interaction patterns and evolution. A programming model must include the main following features

• Mechanisms for grid particle discovery,
• Mechanisms for particle aggregation,
• Constructs for single and aggregate particle evolution,
• Protocols and operations for particle communication, and
• Techniques for data and knowledge storing and discovery.

Those features must be devised departing from current Grid programming models even if they must guarantee the basic Grid computing principles.

A programming model for self-organizing knowledge grids should integrate cellular automata and nature inspired paradigms with peer-to-peer programming mechanisms and ontology-based Grid programming techniques. Those research fields may contribute in constructing a self-organizing knowledge grid programming model that will drive the development of self-organizing knowledge grids as future generation pervasive Grids.

Self-organizing knowledge grids can be effectively used for implementing knowledge-intensive pervasive applications. For example, they can provide the basic infrastructure for ambient intelligence applications. In this scenario each resource (i.e., a sensor, a computer, or a generic device) can be seen as a grid particle that exports its specific features and services and, at the same time, implements all the mechanisms defined by the self-organizing knowledge grid computing model.

Other significant application areas of self-organizing knowledge grids are decentralized and mobile information systems handing with large-scale information sources and collaborative information systems where each grid particle will represent a single node of the system acting as information provider or requestor or as a mediator between nodes that cooperate in achieving a common goal.

References
1. M. Cannataro and D. Talia, "Semantics and Knowledge Grids: Building the Next-Generation Grid", IEEE Intelligent Systems, vol. 19, no 1. pp. 56-63, 2004.
2. R. Want, T. Pering, "System Challenges for Ubiquitous & Pervasive Computing" Proc. ICSE, pp. 9-14, 2005.
3. J. M. Kahn, R. H. Katz and K. S. J. Pister, "Next Century Challenges: Mobile Networking for Smart Dust", ACM/IEEE Intl. Conf. on Mobile Computing and Networking (MobiCom 99), Seattle, WA, August 17-19, 1999.
4. Le. W. McKnight, J. Howison, S. Bradner, "Wireless Grids", IEEE Internet Computing, July/August 2004.
5. J. Blythe et al., "Transparent Grid Computing: A Knowledge-Based Approach," Proc. 15th Innovative Applications of Artificial Intelligence Conference (IAAI 03), AAAI Press, 2003.

Domenico Talia is a professor of Computer Engineering at the Faculty of Engineering, University of Calabria, Italy, http:// si.deis.unical.it/~talia Show Article Preview...