Articles

Approach to achieving coherence of distributed data in multiagent systems

Increasingly rising requirements to computational capability of modern computer systems along with necessity of minimizing their cost lead to change of the paradigm, from buildup of complexity of individual devices to creation of distributed systems consisting of many relatively inexpensive nodes. This trend is very topical for communications systems where the above requirements are complemented with heightened reliability and scalability requirements. However, the existing distributed systems often have some central manager which does not allow using all advantages of such systems. This study focuses on elaboration of a multiagent interaction mechanism, which fully distributed highly reliable and easily scalable solutions can be based on.

Separate scientific discipline of multiagent systems (MAS) was formed in 1980s, and in the mid-nineties, this discipline received wide recognition [1, p.13]. Over the next 15 years, the increasing scope of studies in this field revealed the necessity of systematizing the acquired knowledge and led to the first thematic monographies issued both in Russia [2] and abroad [1, 3–4].

In the early 2000s, the agent-oriented approach was widely applied for distributed solution of complex tasks in computer simulation, organization of operation of multirobot systems, and other areas [2, p. 15]. Today, the multiagent technologies penetrate even into traditionally conservative (in view of requirement of a high level of safety) areas such as power engineering [5], and issues of organization of multirobot systems are growing more urgent both in civil and in military sectors [6] highlighting such tasks as perimeter monitoring, communication support, disaster control, etc.

Having segregated from the classical artificial intelligence field, MASs migrated from the centralized problem solving approach to the decentralized one, assuming that an individual agent can possess only limited knowledge, and interaction within a group of agents would be needed to solve a problem. This determined the conceptual newness of the MAS based solutions [2, p. 15]. The further development of this discipline was stimulated by expectations of increased reliability, flexibility and scalability of such systems [3, p. 8], i.e. qualities which can be provided in the decentralized multiprocessor systems more easily than in the classical ones [7, p. 12].

However, although simplifying creation of the final distributed solutions, MASs require the basic infrastructural mechanisms to be in place to enable interaction between the agents. As such, the operating systems usually offer the message exchange functions only (by addressing or broadcasting), while all the other functions shall be created by the application programmer on his own. This causes some difficulties as parallel programming, especially programming of multiprocessor parallel systems, requires special knowledge and thus originates a separate discipline in programming with its own educational programs and studies.

To make further explanation more convenient, we subdivide all the interaction mechanisms in MASs into three hierarchic levels: the lower level enables communication in general; the upper level determines semantics of information to be transferred; and the medium level based on the lower one is MAS-specific and solves the system-specific tasks, allowing the upper level to stay focused on semantics that depends on what a particular system was created for.

In this context, the research problem, the approach to which is presented in this paper, is to develop and substantiate the medium-level mechanism for providing agent-to-agent interaction in the multiagent systems in order to include the research results into the Russian MAKS real-time operating system which simplifies creation of multiagent systems. The mechanism should be based on message exchange functions, solve basic MAS problems, and provide the application programmer with possibility of relatively simple implementation of traditionally complex high-level and context-dependent capabilities such as redundancy, hot replacement of equipment, scaling, etc.

The term "multiagent" implies presence of several agents and therefore several sources of potentially different knowledge (information). The term "system" implies further coordination of their activities. So, the basic task of a MAS is to guarantee coherence of knowledge within the system. In other words, information shall be exchanged in MAS so that information consistency could be guaranteed in the various nodes of the system. The mechanism to be created would solve this problem.

There is a "blackboard" concept [8] in the MAS theory which describes the system of interaction of several "sources of knowledge" with some common data structure. The concept is a good approximation to our problem, and it can be involved. However, as we speak about a decentralized system, we will expand the initial concept by replacing the central storage with the distributed one. The renewed concept can be called "virtual blackboard". This concept is also known in the multiprocessor computer system theory as distributed shared memory (DSM) [9]. Issues to be considered during creation of such systems are described, for example, in [10]. The key issue here is the consistency model ensuring its coherence. The system is coherent if the value returned by the reading operation is always the same as the value written before by the nearest in time operation to the same address [11]. Though the problem of coherence originated as far back as the processor cache appeared, it represents the main complexity in creating DSM systems as its DSM version has many specific issues [11].

In addition to general requirements to such systems, we shall introduce one more requirement: it is required to provide high reliability of solution in situations when individual nodes/agents may "fall" out of the system (because of communication problems, breakage, etc.). It notably narrows down the range of possible engineering solutions and introduces the new problems which are less commonly considered in the multiprocessor system organization theory.

Two strategies or models can be outlined to solve the memory coherence providing task: invalidation and write-broadcast [11]. The first one allows for only one owner for each distributed object: this reduces overhead expenses for transfer of changed data. The second one requires renewal of data in all duplicate nodes after each write operation. The write-broadcast approach is considered less often as overhead expenses required to organize coherence are very high. However, this approach is well applicable in our situation as it requires quickest possible distribution of changed information to all nodes in the system preventing them from being unique. According to the classification adopted in [9], we can describe the required system as replication (allowing many duplicates of the same data), multiple reader/single writer (MRSW allowing for parallel reading of the same data by many nodes, but permitting write operation to only one node at a time) software (not dependent on hardware characteristics and software-based) algorithm.

In general, the algorithm implemented at the operating system (OS) level can operate as described in Table 1.

Memory coherence providing algorithm
Table 1.
Operation on distributed object d List of instructions of operation
Reading
  1. While (d is disabled), wait
  2. Return reading result
Writing
  1. Request for permission to lock d from all system's agents
  2. If (denial received), cancel lock; wait for random interval; proceed to Para 1
  3. Write d
  4. Send information on release of d and the new value of d
Permitting for lock
  1. While (local operations on d are taking place), wait
  2. Disable d
  3. Give permission
Release message handler
  1. Write the new value of d
  2. Release d


The algorithm shown in Table 1 describes the solution schematically; however, when presented in the simplified form, it contains the following weak points:

  1. Potentially high traffic requirement to provide coherence, especially in case of frequent memory accesses and great number of agents. Possible solution is to freeze sampling rate of operations or to control it automatically.
  2. Perpetual blocking in case of disconnection of agent immediately after object is locked by this agent. Possible solution is to introduce timeouts for corresponding operations.
  3. Loss of coherence in case of disconnection of agent while object release notifications are sent. Here, some agents will receive the new value while others will release the object by timeout without having received the new value. This problem can be brought to known in cryptography "Byzantine Generals problem" which is described and solved, for example, in [12].


The further studies may be aimed at eliminating the said deficiencies (based on the same principled approach), developing the appropriate algorithm in practice, and calculating its characteristics. The solution can be presented in several versions depending on the application scenarios, for example, in the control agent redundancy problem, read and write operations are carried out by only one (active) agent at a time, while in the joint data acquisition problems the operations can be carried out by several agents simultaneously. Many of the modern publications on the issues raised here demonstrate the topical nature of the matter, and the results of the appropriate studies will be considered in the further work.

REFERENCES

  1. Wooldridge M. An Introduction to MultiAgent Systems Second Edition. — Wiley, 2009. — 484 p. — ISBN: 0470519460.
  2. V.B. Tarasov. From multiagent systems to intelligent organizations: philosophy, psychology, and informatics // Moscow, Editorial URSS, 2002 – 352 p. – ISBN: 5836003300.)
  3. Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence / Ed. by G. Weiss. — The MIT Press, 1999. — 643 p. — ISBN: 0262232030.
  4. Shoham Y., LeytonBrown K. Multiagent Systems: Algorithmic, GameTheoretic, and Logical Foundations. — Cambridge University Press, 2008. — 504 p. — ISBN: 0521899435.
  5. Liang H., Abdrabou A., Choi B. J. et al. Multiagent coordination in microgrids via wireless networks // IEEE Wireless Communications. — 2012. — Vol. 19, no. 3. — P. 14–22.
  6. Breitenmoser A., Schwager M., Metzger J.-C. et al. Voronoi coverage of non-convex environments with a group of networked robots // In processing of the IEEE International Conference on Robotics and Automation (ICRA). — Anchorage, Alaska, USA: 2010. — P. 4982–4989.
  7. A.M. Andreev. Multiprocessor computer systems: theoretical analysis, mathematical models and application: Tutorial / A.M. Andreev, G.P. Mozharov, V.V. Suzev. — Moscow: the Bauman Moscow State Technical University, 2011 – 332 p.
  8. Engelmore R., Morgan T. Blackboard systems: edited by Robert Engelmore, Tony Morgan. — Addison Wesley Publishing Company, 1988.
  9. Protic J., Tomasevic M., Milutinovic V. Distributed shared memory: concepts and systems // IEEE Parallel Distributed Technology: Systems Applications. — 1996. — Summer. — Vol. 4, no. 2. — P. 63–71.
  10. Vasava H. D., Rathod J. M. A Survey of Software based Distributed Shared Memory (DSM) Implementation Methodologies for Multiprocessor Environments // International Journal of Innovative Research in Science, Engineering and Technology. — 2013. — Vol. 2, no. 7.
  11. Li K., Hudak P. Memory Coherence in Shared Virtual Memory Systems // ACM Trans. Comput. Syst. — 1989. —November. — Vol. 7, no. 4. — P. 321–359.
  12. B.A. Gueninson, L.A. Pankova, E.A. Trakhtenguerts. Fail-safe methods for providing mutual information coherence in distributed computer systems. — Autoimatics and Telemechanics — 1989. — No. 5. — p.p. 3-18.

 

P.V. Boyko
AstroSoft

Get In Touch

  • Gelsingforsskaya 3, corpus 11D
    194044, St. Petersburg, Russia
  • +79522068225
  • This email address is being protected from spambots. You need JavaScript enabled to view it.