Stochastic Petri net-based modeling and formal analysis of fault tolerant Contract Net Protocol

Abstract

Contract Net Protocol (CNP) is probably the most widely used task allocation protocol in distributed multi-agent systems (MAS). To cope with real-world applications, this protocol must be expanded by addressing some major challenging issues in the current distributed systems. Temporal interaction aspects and reliability issues of such systems, critical to guaranteeing performance, are the focus of this paper. Many researchers have proposed various methods to expand and to improve CNP but those challenges have not been much addressed in a formal way. To cope with these limitations, this paper proposes a Petri net-based model that extends the conventional contract net with real time constraints, often defined as interaction duration and message deadlines, and fault tolerance to handle the agent death exception. Our aim is, hence, to devise an extended CNP that achieves the reliability of the manager agent in the case of contractor crash failure while operating in an open and large scale multi-agent system under time constraints. To address the challenge problem of crash failure detection of the contractor in CNP, we propose to formally model the watchdog/heartbeat mechanism into the communication between the manager and the contractor. Using such mechanism, the manager can detect the crash failure on time and may hence trigger an appropriate recovery procedure to move the system into a safe and a consistent state. The proposed extended CNP model is developed using stochastic timed colored Petri nets which include systematic specification, design and implementation of components of the system. Various useful results will be drawn by simulation as well as state space analysis. This formal analysis shows that the protocol terminates correctly either in a safety case or in a failure situation. It also proves that the protocol meets the key properties namely model correctness, deadline respect, absence of deadlocks and livelocks, absence of dead code, agent terminal states consistency, concurrency, and validity.

Keywords

Multiagent systems negotiation protocols Contract Net Protocol fault tolerance stochastic timed colored Petri nets

Get full access to this article

View all access options for this article.

References

Aized, Modelling and analysis of multiple cluster tools system with random failures using coloured Petri net, The International Journal of Advanced Manufacturing Technology 50(9–12) (October 2010), 897–906.

Aknine,

Pinson and

M.F.

Shakun, An extended multi-agent negotiation protocol, Journal of Autonomous Agents and Multi-Agent Systems 8(1) (2004), 5–45. doi:10.1023/B:AGNT.0000009409.19387.f8.

Ball and

Butler, Event-B patterns for specifying fault-tolerance in multi-agent interaction, in: Lecture Notes in Computer Science, Vol. 5454, 2009, pp. 104–129. doi:10.1007/978-3-642-00867-2_6.

Billington and

Gupta, Effectiveness of coloured Petri nets for modelling and analysing the Contract Net Protocol, in: Proc. of the Eighth Workshop and Tutorial on Practical Use of Coloured Petri Nets and the CPN Tools, Aarhus, Denmark, 2007, pp. 49–65.

Bosse,

D.N.

Lam and

K.S.

Barber, Tools for analyzing intelligent agent systems, The International Journal of Web Intelligence and Agent Systems 6(4) (2008), 355–371, IOS Press.

Boukredera,

Maamri and

Aknine, A timed colored Petri-net-based modeling for Contract Net Protocol with temporal aspects, in: Proc. of the Seventh International Multi-Conference on Computing in the Global Information Technology (ICCGI 2012), Venice, Italy, June 2012, pp. 40–45.

Boukredera,

Maamri and

Aknine, Modeling and analysis of reliable Contract Net Protocol using timed colored Petri nets, in: Proc. of 2013 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT-2013), Atlanta, USA, 2013, pp. 17–24.

F.D.J.

Bowden, A brief survey and synthesis of the roles of time in Petri nets, Journal of Mathematical and Computer Modelling 31(10–12) (2000), 55–68.

Cabac, Modeling agent interaction with AUML diagrams and Petri nets, Diploma thesis, University of Hamburg, Department of Computer Science, Germany, 2003.

10.

T.D.

Chandra and

Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM) 43(2) (March 1996), 225–267. doi:10.1145/226643.226647.

11.

Changyou and

Haiyan, An improved Contract Net Protocol based on concurrent trading mechanism, in: Proc. of the 2011 Fourth International Symposium on Computational Intelligence and Design (ISCID), Vol. 2, Washington, DC, USA, 2011, pp. 318–321.

12.

CPN tools homepage, Retrieved January, 2015, from cpntools.org/.

13.

Dellarocas,

Klein and

J.A.

Rodriguez-Aguilar, An exception-handling architecture for open electronic marketplaces of contract net software agents, in: Proc. of the Second ACM Conference on Electronic Commerce (EC’00), New York, NY, USA, 2000, pp. 225–232. doi:10.1145/352871.352896.

14.

Dragoni, Fault tolerant knowledge level inter-agent communication in open multi-agent systems, Technical report UBLCS-2006-5, Bologna, 2006.

15.

Dragoni and

Gaspari, Crash failure detection in asynchronous agent communication languages, Journal of Autonomous Agents and Multi-Agent Systems 13(3) (November 2006), 355–390. doi:10.1007/s10458-006-0006-y.

16.

Foundation for Intelligent Physical Agents, FIPA modeling area: Temporal constraints, Retrieved May 10, 2012, from http://www.fipa.org.

17.

Hadj-Kacem,

Regayeg and

Jmaiel, ForMAAD: A formal method for agent-based application design, The International Journal of Web Intelligence and Agent Systems 5(4) (2007), 435–454, IOS Press.

18.

Haider,

N.R.

Ansari,

Akbar,

M.R.

Perwez and

K.M.

Ghori, Fault tolerance in distributed paradigms, in: Proc. of CSIT, The 2011 International Conference on Computer Communication and Management, Vol. 5, IACSIT Press, Singapore, 2011.

19.

Harper, Programming in Standard ML, Working draft, Carnegie Mellon University, Pittsburgh, PA, 2011.

20.

F.S.

Hsieh, Automated negotiation based on contract net and Petri net, in: E-Commerce and Web Technologies, Lecture Notes in Computer Science, Vol. 3590, 2005, pp. 148–157. doi:10.1007/11545163_15.

21.

M.P.

Huget and

Odell, Representing agent interaction protocols with agent UML, in: Proc. of the Third International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2004), New York, USA, July 2004.

22.

Inverno,

Fisher,

Lomuscio,

Luck,

de Rijke,

Ryan and

Wooldridge, Formalisms for multi-agent systems, The Knowledge Engineering Review 12(3) (September 1997), 315–321. doi:10.1017/S0269888997003068.

23.

Jagga and

Ranna, Developing reliability model in Contract Net Protocol, The International Journal of Research in IT & Management (IJRIM) 2(2) (2012), (ISSN 2231-4334).

24.

Jensen and

L.M.

Kristensen, Coloured Petri Nets – Modelling and Validation of Concurrent Systems, Springer, Berlin, July 2009.

25.

Kahloul,

Barkaoui and

Sahnoun, Using AUML to derive formal modelling agents interactions, in: The Third International Conference on Computer Systems and Applications (AICCSA), IEEE Computer Society Press, 2005, pp. 109–116.

26.

Klein,

J.A.

Rodríguez-Aguilar and

Dellarocas, Using domain-independent exception handling services to enable robust open multi-agent systems: The case of agent death, Journal of Autonomous Agents and Multi-Agent Systems 7(1) (July 2003), 179–189. doi:10.1023/A:1024145408578.

27.

Object Management Group, Agent unified modeling language, Retrieved May 15, 2012, from http://www.AUML.org.

28.

Ohko,

Hiraki and

Anzai, Reducing communication load on contract net by case-based reasoning: Extension with directed contract and forgetting, in: Proc. of the First International Conference on Multi-Agent Systems, MIT Press, Cambridge, MA, 1996.

29.

Parsons and

Klein, Towards robust multi-agent systems: Handling communication exceptions in double auctions, in: Proc. of the Third International Joint Conference on Autonomous Agents and Multiagent Systems AAMAS, New York, NY, USA, 2004, pp. 1482–1483.

30.

J.M.

Serrano and

Ossowski, A compositional framework for the specification of interaction protocols in multiagent organizations, The International Journal of Web Intelligence and Agent Systems 5(2) (2007), 197–214, IOS Press.

31.

Shujuan,

Tian and

Liang, A Petri-net-based modeling framework for automated negotiation protocols in electronic commerce, in: Lecture Notes in Computer Science, Vol. 4078, 2009, pp. 324–336. doi:10.1007/978-3-642-03339-1_26.

32.

R.G.

Smith, The Contract Net Protocol: High-level communication and control in a distributed problem solver, IEEE Transactions on Computers 12 (1980), 1104–1113. doi:10.1109/TC.1980.1675516.

33.

Valmari, The state explosion problem, in: Lecture Notes in Computer Science, Vol. 1491, 1998, pp. 429–528. doi:10.1007/3-540-65306-6_21.

34.

W.M.P.

van der Aalst,

K.M.

Va Hee and

H.A.

Reijers, Analysis of discrete-time stochastic Petri nets, Journal of Statistica Neerlandica 54(2) (2000), 237–255. doi:10.1111/1467-9574.00139.

35.

J.Z.

Wang and

Vanninen, Self-configuration protocols for P2P networks, The International Journal of Web Intelligence and Agent Systems 4(1) (2006), 61–76, IOS Press.

36.

Webel,

Fliege,

Geraldy and

Gotzhein, Developing reliable systems with SDL design patterns and design components, in: ISSRE04 Workshop on Integrated-Reliability with Telecommunications and UML Languages, 2004.

37.

Xie and

Wang, A group cooperative decision support system based on extended contract net, Journal of Group Decision and Negotiation 23(5) (2014), 1191–1217. doi:10.1007/s10726-013-9369-z.

38.

Xu,

Padgham,

Mbala and

Harland, Tracking reliability and helpfulness in agent interactions, The International Journal of Web Intelligence and Agent Systems 5(1) (2007), 31–46, IOS Press.