Abstract: We discuss the problem of connectivity within large-scale dynamic distributed information systems. Ad hoc system can adapt themselves through resource management or reconfiguration to achieve specific goals, such as functions, performance, energy budget and reliability. One of the mostly important goals is to keep a possibility of routing for any two nodes of the distributed system. Structure of the system can be described by a time-graph. In some moments of the time the structure of a network changes: new nodes can be included into the network and old nodes can be deleted. Thus the connectivity property of the time-graph is a logical function of time. A cause of disconnection may be technical (hardware failures, low energy, server overloading etc) or organizational (information secure, regular breaks or random interruptions). To improve the quality of service we have to control the distributed information system structure. The first step of a self-management (autonomic) system design is to describe permissible structures and forbidden structures. We propose to use the well-known method of graph grammars for this purpose. A finite set of graph grammar rules defines an infinite (but countable) set of permissible structures. An inference process allows us to get some permissible graph after doing of a finite sequence of steps. In this work we solve the problem of a set of graph grammar rules description for such property of graphs as connectivity. A detailed description of the rule set is used for rewriting of any graph (connected or disconnected) to a connected graph. Also we discuss a second step of a self-aware system design: including of the graph grammar into a feedback control cycle. An autonomic system has the property of selfawareness, i.e. the system contains its model and manages itself using this model. During a life-time cycle the current model can be compared with the permissible set described by graph grammar. If the current model isn’t belong to the permissible set then the distributed system turns a connectivity renewal process on. Some problems of graph grammar algorithms complexity are discussed.

Keywords: time-graph, grammar, autonomic system, ad hoc system.

ACM Classification Keywords: H. Information Systems: H.3 Information Storage and Retrieval: H.3.4 Systems and Software – Distributed systems. C. Computer Systems Organization: C.2 Computer-Communication? Networks: C.2.4 Distributed Systems – Distributed applications.

Link:

CONNECTIVITY CONTROL IN AD HOC SYSTEMS: A GRAPH GRAMMAR APPROACH

Alexander Mikov, Alexander Borisov

http://www.foibg.com/ijima/vol02/ijima02-01-p04.pdf