FSP and FLTL framework for specification and verification of middle-agents

Bădică, Amelia; Bădică, Costin

doi:10.2478/v10006-011-0001-6

Abstract

Agents are a useful abstraction frequently employed as a basic building block in modeling service, information and resource sharing in global environments. The connecting of requester with provider agents requires the use of specialized agents known as middle-agents. In this paper, we propose a formal framework intended to precisely characterize types of middle-agents with a special focus on matchmakers, brokers and front-agents by formally modeling their interactions with requesters and providers. Our approach is based on capturing interaction protocols between requesters, providers and middle-agents as finite state processes represented using FSP process algebra. The resulting specifications are formally verifiable using FLTL temporal logic. The main results of this work include (i) precise specification of interaction protocols depending on the type of middle-agent (this can also be a basis for characterizing types of middle-agents), (ii) improvement of communication between designers and developers and facilitation of formal verification of agent systems, (iii) guided design and implementation of agent-based software systems that incorporate middle-agents.

References

Alagar, V. and Holliday, J. (2002). Agent types and their formal descriptions, Technical Report COEN-2002-09-19A, Santa Clara University, Santa Clara, CA.
Search in Google Scholar
Bergstra, J., Ponse, A. and Smolka, S. (2001). Handbook of Process Algebra, Elsevier Science, Amsterdam.
Search in Google Scholar
Brazier, F. M. T., Cornelissen, F., Gustavsson, R., Jonker, C. M., Lindeberg, O., Polak, B. and Treur, J. (2004). Compositional verification of a multi-agent system for one-to-many negotiation, Applied Intelligence 20(2): 95-117.10.1023/B:APIN.0000013334.33853.0c
Search in Google Scholar
Bădică, A. and Bădică, C. (2008a). Conceptualizing interactions with matchmakers and front-agents using formal verification methods, in D. Dochev, M. Pistore and P. Traverso (Eds.), Proceedings of the 13th International Conference on Artificial Intelligence: Methodology, Systems, Applications (AIMSA 2008), Lecture Notes in Artificial Intelligence, Vol. 5253, Springer-Verlag, Berlin, pp. 390-394.
Search in Google Scholar
Bădică, A. and Bădică, C. (2008b). Formal specification of matchmakers, front-agents, and brokers in agent environments using FSP, Proceedings of the 6th International Workshop on Modelling, Simulation, Verification and Validation of Enterprise Information Systems (MSVVEIS 2008), Barcelona, Spain, pp. 9-18.
Search in Google Scholar
Bădică, A. and Bădică, C. (2008c). Formalizing agent-based english auctions using finite state process algebra, Journal of Universal Computer Science 14(7): 1118-1135.
Search in Google Scholar
Bădică, A. and Bădică, C. (2008d). Modeling interactions in agent-based English auctions with matchmaking capabilities, in C. Bădică, G. Mangioni, V. Carchiolo and D. D. Burdescu (Eds.), Intelligent Distributed Computing, Systems and Applications (IDC 2008), Studies in Computational Intelligence, Vol. 162, Springer-Verlag, Berlin, pp. 45-54.10.1007/978-3-540-85257-5_5
Search in Google Scholar
Bădică, A. and Bădică, C. (2008e). Specification and verification of agent interactions in matchmaking processes using FSP and FLTL, Proceedings of the 23rd International Symposium on Computer and Information Sciences (ISCIS 2008), Istanbul, Turkey, pp. 1-6.10.1109/ISCIS.2008.4717962
Search in Google Scholar
Bădică, A. and Bădică, C. (2009a). Formalizing agent interactions in matchmaking processes using FSP and FLTL, Scientific Bulletin of "Politehnica" University of Timisoara, Transactions on Automatic Control and Computer Science 54(68)(1): 13-18.
Search in Google Scholar
Bădică, A. and Bădică, C. (2009b). Specification and verification of an agent-based auction service, in G. A. Papadopoulos, W. Wojtkowski, G. Wojtkowski, S. Wrycza, and J. Zupancic (Eds.) Information System Development. Towards a Service Provision Society (ISD 2008), Springer-Verlag, New York, NY, pp. 239-248.
Search in Google Scholar
Bădică, A., Bădică, C. and Liţoiu, L. (2003). Role activity diagrams as finite state processes, Proceedings of the 2nd International Symposium on Parallel and Distributed Computing (ISPDC 2003), Ljubljana, Slovenia, pp. 15-22.
Search in Google Scholar
Bădică, A., Bădică, C. and Liţoiu, L. (2007). Middle-agents interactions as finite state processes: Overview and example, Proceedings of the 16th IEEE International Workshop on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE 2007), Paris, France, pp. 12-17.
Search in Google Scholar
Bădică, A., Bădică, C., Popescu, E. and Scafes, M. (2009). A process algebraic framework for service coordination, Proceedings of the 5th International Symposium on Applied Computational Intelligence and Informatics (SACI 2009), Timişoara, Romania, pp. 515-520.
Search in Google Scholar
Bădică, C., Ganzha, M. and Paprzycki, M. (2007). Developing a model agent-based e-commerce system, in J. Lu, G. Zhang and D. Ruan (Eds.), E-Service Intelligence: Methodologies, Technologies and Applications, Studies in Computational Intelligence, Vol. 55, Springer-Verlag, Berlin, pp. 555-578.
Search in Google Scholar
Clarke, E. M., Emerson, E. A. and Sistla, A. P. (1986). Automatic verification of finite-state concurrent systems using temporal logic specifications, ACM Transactions on Programming Languages and Systems 8(2): 244-263.10.1145/5397.5399
Search in Google Scholar
Decker, K., Sycara, K. P. and Williamson, M. (1997). Middle-agents for the internet, Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI'97), Nagoya, Aichi, Japan, Vol. 1, pp. 578-583.
Search in Google Scholar
D'Ippolito, N., Fischbein, D., Chechik, M. and Uchitel, S. (2008). MTSA: The modal transition system analyser, Proceedings of the 23rd IEEE/ACM International Conference on Automated Software Engineering, ASE'08, L'Aquila, Italy, pp. 475-476.
Search in Google Scholar
Dobriceanu, A., Bîscu, L., Bădică, A. and Bădică, C. (2009). The design and implementation of an agent-based auction service, International Journal of Agent Oriented Software Engineering 3(2/3): 188-211.10.1504/IJAOSE.2009.023633
Search in Google Scholar
Dwyer, M. B., Avrunin, G. S. and Corbett, J. C. (1999). Patterns in property specifications for finite-state verification, Proceedings of the 21st International Conference on Software Engineering (ICSE 1999), Los Angeles, CA, USA, pp. 411-420.
Search in Google Scholar
Esterline, A., Rorie, T. and Homaifar, A. (2006). A process-algebraic agent abstraction, in C. A. Rouff, M. Hinchey, J. Rash, W. Truszkowski and D. Gordon-Spears (Eds.), Agent Technology from a Formal Perspective, NASA Monographs in Systems and Software Engineering, Springer-Verlag, London, pp. 88-137.10.1007/1-84628-271-3_4
Search in Google Scholar
Fasli, M. (2007). Agent Technology for E-Commerce, JohnWiley & Sons, Chichester.
Search in Google Scholar
Fokkink, W. (2007). Texts in Theoretical Computer Science, EATCS Series, Springer-Verlag, Berlin/Heidelberg.
Search in Google Scholar
Foster, H., Uchitel, S., Magee, J. and Kramer, J. (2006). LTSAWS: A tool for model-based verification of web service compositions and choreography, in L. J. Osterweil, H. D. Rombach and M. L. Soffa (Eds.), Proceedings of the 28th International Conference on Software Engineering (ICSE 2006), Shanghai, China, pp. 771-774.
Search in Google Scholar
Goh, S., Chhetri, M. B. and Kowalczyk, R. (2007). JADE-FSM-engine: A deployment tool for flexible agent behaviours in JADE, Proceedings of the 2007 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, IAT'2007, Silicon Valley, CA, USA, pp. 524-527.
Search in Google Scholar
Hennicker, R. and Ludwig, M. (2005). Property-driven development of a coordination model for distributed simulations, in M. Steffen and G. Zavattaro (Eds.), Formal Methods for Open Object-Based Distributed Systems, Lecture Notes in Computer Science, Vol. 3535, Springer, Berlin/Heidelberg, pp. 290-305.10.1007/11494881_19
Search in Google Scholar
Hoare, C. A. R. (1985). Communicating Sequential Processes, Prentice Hall International Series in Computer Science, Upper Saddle River, NJ.
Search in Google Scholar
Hristozova, M. and Sterling, L. (2003). Experiences with ontology development for value-added publishing, in S. Cranefield, T. W. Finin, V. A. M. Tamma and S. Willmott (Eds.), Proceedings of the International Workshop on Ontologies in Agent Systems (OAS 2003), CEUR Workshop Proceedings, Vol. 73, pp. 17-24.
Search in Google Scholar
Klusch, M. and Sycara, K. P. (2001). Brokering and matchmaking for coordination of agent societies: A survey, in A. Omicini, F. Zambonelli, M. Klusch and R. Tolksdorf (Eds.), Coordination of Internet Agents: Models, Technologies, and Applications, Springer, Berlin/Heidelberg/New York, NY, pp. 197-224.10.1007/978-3-662-04401-8_8
Search in Google Scholar
Magee, J. and Kramer, J. (2006). Concurrency. State Models and Java Programs, 2nd Edn., John Wiley & Sons, Chichester.
Search in Google Scholar
Mbala, A., Padgham, L. and Winikoff, M. (2006). Design options for subscription managers, in G. A. Vouros and T. Panayiotopoulos (Eds.), Agent-Oriented Information Systems III, Lecture Notes in Computer Science, Vol. 3529, Springer, London, pp. 259-274.10.1007/11916291_18
Search in Google Scholar
Merayo, M., Núñez, M., and Rodríguez, I. (2007). Specification of multi-agent systems by using EUSMs, Proceedings of the International Symposium on Fundamentals of Software Engineering (FSEN'2007), Lecture Notes in Computer Science, Vol. 4767, Springer, Berlin/Heidelberg/New York, NY, pp. 318-333.
Search in Google Scholar
Miller, T. and McBurney, P. (2007). Using constraints and process algebra for specification of first-class agent interaction protocols, Engineering Societies in the Agents World VII (ESAW 2006), Lecture Notes in Computer Science, Vol. 4457, Springer, Berlin/Heidelberg/New York, NY, pp. 245-254.
Search in Google Scholar
Milner, R. (1999). Communicating and Mobile Systems: The π-Calculus, Cambridge University Press, Cambridge.
Search in Google Scholar
Podorozhny, R. M., Khurshid, S., Perry, D. E. and Zhang, X. (2007). Verification of multi-agent negotiations using the alloy analyzer, Proceedings of the 6th International Conference Integrated Formal Methods (IFM'2007), Lecture Notes in Computer Science, Vol. 4591, Springer, Berlin/Heidelberg/New York, NY, pp. 501-517.
Search in Google Scholar
Rahimi, S., Cobb, M., Ali, D. and Petry, F. (2002). A modeling tool for intelligent-agent based systems: Api-calculus, in V. Loia (Ed.), Soft Computing Agents: A New Perspective for Dynamic Systems, Frontiers in Artificial Intelligence and Applications, IOS Press, Amsterdam, pp. 165-186.
Search in Google Scholar
Rouff, C., Rash, J., Hinchey, M. and Truszkowski, W. (2006). Formal methods at NASA Goddard Space Flight Center, in C. A. Rouff, M. Hinchey, J. Rash, W. Truszkowski and D. Gordon-Spears (Eds.), Agent Technology from a Formal Perspective, NASA Monographs in Systems and Software Engineering, Springer-Verlag, London, pp. 287-309.10.1007/1-84628-271-3_10
Search in Google Scholar
Wang, F. (2002). Self-organising communities formed by middle agents, Proceedings of the 1st International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS'02, Bologna, Italy, pp. 1333-1339.
Search in Google Scholar
Wong, H. C. and Sycara, K. (2000). A taxonomy of middle-agents for the Internet, Proceedings of the 4th International Conference on MultiAgent Systems (ICMAS-2000), Boston, MA, USA, pp. 465-466.
Search in Google Scholar
Xu, D.-X., El-Ariss, O., Xu, W.-F. and Wang, L.-Z. (2009). Aspect-oriented modeling and verification with finite state machines, Journal of Computer Science and Technology 24(5): 949-961.10.1007/s11390-009-9269-5
Search in Google Scholar
Yarom, I., Rosenschein, J. S. and Goldman, C. V. (2003). The role of middle-agents in electronic commerce, IEEE Intelligent Systems 18(6): 15-21.10.1109/MIS.2003.1249165
Search in Google Scholar
Zhang, P., Muccini, H. and Li, B. (2010). A classification and comparison of model checking software architecture techniques, Journal of Systems and Software 83(5): 723-744.10.1016/j.jss.2009.11.709
Search in Google Scholar

FSP and FLTL framework for specification and verification of middle-agents

Abstract

Paradigm

My account