Resource federation in grid computing (Foster et al., 1999, 2001) still requires extensively intervention of resource administrator which is time and cost consuming. This limitation leads to the idea of applying the autonomous intelligent agent to ease the process of resource federation (Foster et al., 2004). The participation and contribution of resources are based on a set of rules and regulations, namely local administrative policies. The local administrative policies can be further detailed into accounting policy, access control policy, resource usage policy and more (Foster et al., 2001). In this study, resource usage policy (as shown in Fig. 1) specifies the requirements and limits on particular resources during resource federation between various participants. A consensus among the participants is achieved through a bargaining mechanism, which aims at maximizing the satisfaction level during policy negotiation. The policy negotiation involves the satisfaction of policy criteria.
Those criteria listed out the terms and conditions during resource federation, such as the resources to be shared, the participants who are allowed to utilize the resources, and also restrictions of sharing. Policy criteria can utilize a full range of qualitative and quantitative criterion. The matching of criteria between two participants is a complicated process because various types of criteria need to be fulfilled simultaneously. Both participants may not compromise at the beginning of matching, thus, a method to further increase the matching rate is needed. The common approaches, namely Constraint Satisfaction Problem (CSP) (Tsang, 1993) and Multi-Criteria Analysis (MCA) (Cheng et al., 2010), are studied to solve this problem.
CSP (Tsang, 1993) is a problem composed of a finite set of variables. Each of the variables is associated with a finite domain, and a set of constraints that restricted the values the variables can simultaneously take. The task of CSP is to assign a value to each variable satisfying all the constraints. MCA (Cheng et al., 2010) means there are multiple criteria related to a particular decision waiting for a result determination. A single criterion matching emphasizes the optimizing of the corresponding criterion value. However, multi-criteria matching which could achieve the optimal solution for all related criteria is rare and impractical because the complexity is high. As a result, a solution to compromise the satisfaction level in order to generate optimal solution is more preferable. The optimal solution may not satisfy the greatest value in all criteria but the solution is confirmed to be the best combination with highest utility scoring value.
According to the empirical result, maximize the compromise level for both participants may not promise a success in negotiation. Effort is spent to generate a mutual acceptance between participants but failed. Looking for another resource (participant) may not worth to perform since no guarantee for a success. Certain level of toleration in satisfaction can be applied but a comparative model for toleration (how to compensate equally with the amount of toleration) is still an open issue. Conventional automated negotiation approaches mainly solved arguments between two participants with conflict avoidance behaviour. Both participants will preferably withdraw from the negotiation process and looking for others resources when criteria cannot be satisfied. They assume terminating the relationship is a win-win situation since the resource pool has more choices.
As shown in Fig. 2, resource federation in grid environment can be mainly categorized into manual and automated approaches. Manual approaches requires human administrator to perform sequential resource matching. If three different types of resources are required in a resource federation scenario, then the human administrator may need to select and match the corresponding requirements from the available resource pools sequentially. This is believed to be time and cost consuming. Due to the limitation of manual approach, several automated approaches have been introduced. Among various types of implementation techniques, the intelligent agent is the famous adoption in automated approaches. This is due to the agent’s features such as autonomous, flexibility and reactive to environment. These features are discussed and validated in papers (Cheng et al., 2005, 2006, 2010). The automated approaches can further be divided into non-negotiation (Xie & Qi, 2006; Russell et al., 2004) and negotiation techniques (Cheng et al., 2010; Ströbel & Weinhardt, 2003). Non-negotiation techniques are direct resource matchmaking without spaces of bargain. In contrast to non-negotiation techniques, negotiation techniques provide a bargaining mechanism to counter-offer between two agents before striking the final deal.
The purpose of our study is to investigate and propose a conflict resolution model for multi-agent negotiation during resource federation. In order to provide a comprehensive review of possible solutions in agents’ conflict resolution, various types of sophisticated negotiation approaches (e.g. logrolling, bridging, brainstorming, expand the pie) are compared and discussed. A concept of Creative Negotiation (Billikopf, 2003) which yet to be applied in automated conflict resolution with intelligent agent is proposed in this paper. Several technical challenges need to be reviewed during different stages of multi-agent negotiation implementation. The adoption of a Select, Match, Negotiate and Expand (SMNE) protocol (Cheng et al., 2010) helps in illustrating the overall framework of agent negotiation.
2. Resource federation
Resource federation in grid emphasizes a flexible and secure resource sharing mechanism. Higher flexibility of resource policy negotiation and more secure resource accessibility increase the confidence of participants in coordinating their resources. However, the mentioned characteristics bring several challenges during user authentication and authorization, resource access and resource matchmaking. Our research focuses on how to provide a scalable resource federation framework with automated policy negotiation under the domain of resource matchmaking. A comprehensive analysis of the state-of-the-art of resource federation framework is conducted to solve the problem above.
2.1 Why automate the resource federation?
The early work in grid resource federation is to manually select the participants for a Virtual Organization (VO) by VO initiator (administrator). VO is formed among the geographically dispersed participants in order to share their resources. The participant selection process has been improved with the aid of electronic media such as e-mail and e-forum. During the selection, the resource administrators play an important role during the communication since they are responsible in defining the resource usage policies. From various participant selection approaches, the most widespread implementation method is called Virtual Organization Membership Service (VOMS) (Alfieri et al., 2005). The VOMS approach owns a database which contains authorization data that defines specific capabilities and general roles for specific users. The method of proxy-certificate exchange is applied for user identity authentication and job submission during resource federation. The manual participant selection process in VOMS only solves the simple authorization problem. In a large scale resource federation environment, this method is not sufficient since a more challenging problem exists – access control over resources. The access control over resources is defined by the resource usage policies.
The administrators define the access control on each resource in corresponding policy. The resource usage policies help in defining the terms and conditions for resource sharing in a more structural and organized manner. On the other hand, when the VO initiator notifies the system of his intention to create a VO, the VO initiator will impose several resource usage policies (namely VO policies) to specify the requirements of different types of resources. The matchmaking between local administrative policies and VO policies can be implemented with different approaches. The initial common approach depends heavily on the intervention of human administrators. The administrators perform sequential policies matching in order to determine the qualified VO participants. A VO is established after both, local administrator and VO administrator, agreed upon the resource usage policies. This manual approach allows the administrator to be aware of each policy criterion and also assure the most preferable participants are chosen based on administrator perspective. However, as the complexity of policies increase due to the higher flexibility of policy criteria nowadays, the manual approach is become impractical. The limitations of manual policy matching are summarized below:
Policies are difficult to search, organize and manage because the policy criteria is complicated and overloaded,
Manual policy matching tends to be unsuccessful and requires repeatable matching because administrators find difficulty in considering all the policies synchronously,
Lack of global consideration of resource utility since administrators only aware on frequent access policies,
Manual approach increases the time and the cost in management because more effort are needed for human decision-making,
Human administrator is unable to entertain requests in 24/7 (24 hours a day, 7 days a week).
Due to the limitations of manual approach in resource federation, such as overloaded policy management, lower resource satisfaction and optimization, time and effort consuming, several automated approaches are introduced, namely Globus Resource Allocation Manager (GRAM) (Czajkowski et al., 1998) and Condor ((Litzkow et al., 1998). Both methods embedded with heuristic decision-making ability during resource selection. Major routine and trivial administrator workloads such as certificate validation and monitor resource availability have been automated to simplify the selection process. For example, in Condor, a ClassAd mechanism (Raman et al., 1998, 2003) was applied to match arbitrary resource requests with available resource offers. Several components like ClassAd specification, advertising protocol, matchmaking algorithm, matchmaking protocol and claiming protocol are designed in the matchmaking framework. The matchmaker tries to satisfy respective resource provider advertisements constraint (policy terms or criteria) and inform the relevant entities match. Furthermore, a sorted ranking mechanism is applied when multiple resources fulfilled the requirements.
Even though the automated approaches have addressed several limitations of manual approaches, room for improvement still exist. Firstly, resource administrator is required to define policies in a structural format, in order to make those policies more manageable. Secondly, a multi-criteria selection method is needed since different resource administrators may emphasize different criteria on the same kind of resource. Sometimes VO administrator is required to deal with imperfect knowledge on certain criteria during resource selection. The quality of decision-making with automated approach is often being criticized. Thirdly, during resource selection and policy reconciliation, several constraints impose on the resources may hinder a successful federation because VO and local resource administrators have different set of policies (VO policy, for all VO participants to follow during federation; local administrative policy, to control the accessibility of local resource from VO participants). An approach to address proper resource semantics for the definition of the usage and accessibility of resources is needed, such as the research works mentioned in Czajkowski et al., 2004; Dave, 2004; Djordjevic & Dimitrakos, 2004; Moses, 2005 and Naqvi & Mori, 2009.
2.2 Automated approaches in resource federation
As shown in the Fig. 2, automated approaches are categorized into non-negotiation and negotiation methods. Non-negotiation method can perform faster than negotiation method during policy matching. This is because non-negotiation method does not require bargaining on the policy criteria. It just allows the administrator to either accept or reject the listed policies. This method is obviously faster and cheaper because less processing is needed. Besides that, since bargaining is not applied into non-negotiation methods, the policy criteria are easier to be organized. For example, during negotiation process, the upper and lower bound of the criteria value are defined in a policy. This allows participants to compromise according to situation. A function to decide the exact bargaining value for each criterion is incorporated. However, non-negotiation methods can save this effort.
The federation of grid resources using non-negotiation methods included Russell et al., 2004 (a mechanism for securely sharing service instances by using grid computing in a diagnostics environment), Xie & Qi, 2006 (proposed a space-based coordination model to establish diverse VOs with special sharing policies), Network Queuing Environment (a batch submission system allowed users to create and submit job with specific resource requests and monitor the progress) (Cray Inc., 1997), Portable Batch System (provided scheduling execution and routing of batch jobs between different resources) (Bayucan et al., 1999) and Load Sharing Facility (enabled system to redistribute workload among the hosts to improve performance and accessibility to remote resources) (Zhou et al., 1993). Some of these non-negotiation methods provide automated resource discovery and matching mechanism. However, the inflexibility of policy enforcement with static rules prohibits these methods to be applied in recent grid resource federation.
Due to the weaknesses of non-negotiation method, several negotiation methods have been studied. A flexible and robust negotiation method is proposed to solve the limitations of non-negotiation method. The robustness of negotiation addresses the issue of policy reconciliation between parties. The negotiation method must provide fault recovery mechanism during resource federation. For instance, appropriate solution is taken to avoid operation failures in a VO, such as dynamic join and leave for participants, and routine occurrence of resource failures in a large VO.
Legion grid architecture (Grimsaw & Wulf, 1996) provides an object-based approach for resource federation. A simple but generic scheduler defines the access and usage through diverse policies. Legion has highlighted the importance to counteract the fault tolerance during resource federation. According to Grimsaw and Wulh (Grimsaw & Wulf, 1996), writing fault tolerant distributed applications were difficult and error prone, thus, effort and risk in solving this problem must consider in the solution design. This shows the importance of robustness in distributed applications.
Reid G. Smith developed a contract net protocol (Smith, 1980) to specify problem-solving communication and control over the participants in a distributed problem solver. This protocol describes how resources can be distributed among a set of participants. However, no counter-offer and constraints relaxation are allowed in contract net protocol. Four important components of negotiation mechanism are discussed in paper Smith, 1980:
A negotiation is a local process that did not involve centralized control,
There is a two-way exchange of information during negotiation,
Each negotiation participant evaluates the information from his own perspective,
The final agreement of a bargaining is achieved by mutual selection.
Constraint Directed Negotiation (Sathi, 1990) represents the decision-making in negotiation as a solution to Constraint Satisfaction Problem (CSP). The task of CSP is to assign a value to each variable that satisfying all the constraints. Negotiation capability in CSP helps to improve the success rate of bargaining process. The constraint directed negotiation defines the constraints in qualitative mode only, but a complicated system like grid resource federation requires the policy criteria to be both qualitative and quantitative. Therefore, the applicability of constraint directed negotiation in distributed environment is arguable.
Web services-based standards within the context of the Open Grid Services Architecture (OGSA) (Foster et al., 2002) are among the famous adoption of grid technologies recently. The OGSA relies on a set of emerging web services (WS) specifications, such as Web Service Resource Framework (WSRF), Web Service Description Language (WSDL) and WS-Negotiation protocol, within the grid community. The web services with grid-connectivity are giving a name called grid services. Generally, a grid service use Simple Object Access Protocol (SOAP) or Representational State Transfer (REST)-style Extensible Markup Language (XML) enveloper with its own interface described by WSDL. A transaction between service requestor and service provider normally require the negotiability in order to increase the flexibility and efficiency of grid service discovery and matching. Hung et al. (Patrick et al., 2004) proposed the WS-Negotiation protocol to solve this problem. In WS-Negotiation framework, participants perform under provider-requestor relationship where both negotiate on a set of policy criteria. Either participant can determine to negotiate on selective criteria. Later, each participant will sort the criteria according to its significance before bargaining. In general, the WS-Negotiation contained three parts:
Negotiation Message – which describes the format for messages exchanged between negotiation participants,
Negotiation Protocol – which describes the mechanism and rules that negotiation participants should follow, and
Decision-making – which is an internal and private decision process based on negotiation strategies.
In addition, WS-Negotiation also presented a Web Service Level Agreement (WSLA) which is the suggested model in SLA template. Andrieux et al., 2005 investigated the WS-Agreement and mentioned the importance to have a language and a protocol that publicizes what a service provider has to offer, in order to create agreements, as well as having a monitoring service. WS-Negotiation only provides a protocol for one-to-one single round negotiation. Therefore, an advanced version of WS-Agreement which allows multiple-round negotiations is proposed by Waeldrich et al., 2011. The proposed method helps in solving the iterative negotiation problem.
Other automated negotiation methods in the literature included Mobach et al., 2005 which used two-tier negotiation model in WS-Agreement to develop a one-to-many negotiation platform, Sadri et al., 2002 adopted logic-based approach and a shared language for agent communication and negotiation, Binmore & Vulkan, 1999 implemented game theory for automated negotiation, Kasbah electronic agent marketplace (Chavez et al., 1997) adopted CSP for electronic commerce application, Venugopal et al., 2008 proposed an alternate offers protocol for bilateral negotiation during resource reservation, Cheng et al., 2006 adopted artificial intelligence method and one-to-many negotiation framework for resource allocation, Rubinstein alternating protocol (Paurobally et al., 2005) supported one-to-one negotiation on a given policy and Xplore coordination platform (Andreoli & Castellani, 2001) used bi-colored negotiation graph to represent negotiation states.
Compare to manual and automated non-negotiation approaches, automated negotiation approaches have higher flexibility because disputes during policy matching are able to solve with constraints relaxation and bargaining methods. Negotiation approaches can increase participant’s satisfaction because both VO and local administrators can determine and demand for requested SLA. Furthermore, VO and local administrators possibly explore some hidden information (space of negotiation) for conciliation in order to increase the success rate of negotiation.
However, from the negative perspective the automated negotiation approach applies indirect policy matching, thus it consumes more time and cost in policy criteria determination and negotiation. It also requires the administrator to derive and represent his preferences precisely, thus allows the automation of negotiation to proceed accurately. According to Foster et al., 2004, autonomous intelligent agents have been applied to reduce the intervention of resource administrators. They believed the deployment of agents as autonomous problem solvers which act flexibly in uncertain and dynamic environments such as grid will solve the above problems.
2.3 Why applied autonomous agent in negotiation
The basic functionalities of an intelligent agent included autonomous, reactive and goal-oriented. Intelligent agent has been deployed into the grid applications over the past few years. The adoption of intelligent agent into the grid domain is because the grid environments require autonomous and flexible behaviors whereas agent systems need a robust infrastructure to support its functionalities (Foster et al., 2004). Agents are often required to organize themselves into a collective manner and coordinate their actions in order to deliver certain tasks. This is in line with the purpose of VO construction in grid environment. Applying agent technology in resource federation has various benefits over the previous mentioned automated negotiation approaches. Firstly, autonomous agents are designed to have only partial control and knowledge regarding the environment. Agents can communicate and coordinate in order to achieve local and global resource optimization. Secondly, agents are more sophisticated in coordination, collaboration and negotiation through agent communication protocol. This enables the decomposition of complex resource federation problems into individual sub request or task and to be handled by corresponding autonomous agents. The integration between grid and agent will undoubtedly create new challenges in resource federation. Therefore, this paper will further analyze some possible challenges in the mentioned area.
2.3.1 Definition of agent negotiation
Negotiation occurs when somebody want to create something new that neither participant could do on his own, or a problem, conflict or dispute between the participants is required to be resolved (Roy et al., 2009). If two participants are willing to negotiate, they prefer to search for agreement rather than to argue openly. This statement is only valid if the participants expect to give and take. Both participants are required to modify or give in according to their previous proposals. However, the participants involved always face the dilemmas of honesty and truth in making concession. The honesty and truth determine how well a participant exposes and believes in others. This is an important consideration during automated negotiation.
An intelligent agent always explores a wider range of alternatives during negotiation. More alternatives (choices) constantly bring more chances in striking a deal. Normally, an upper limit, Vmax and a lower limit, Vmin for each criterion are set in filtering the alternatives. The filtering process is performed by referring to the existence of zone of agreement between two proposals. As shown in Fig. 3, a zone of agreement exists when the range of value between two participants are overlapped each other. Larger overlapping indicates higher chances in striking a deal during negotiation. Cheng et al., 2005 illustrated how to deal efficiently in a limited zone and find alternatives to satisfy both participants. Generally, a negotiation tactic is used to determine the value (within the upper and lower limits) to be offered in a particular criterion for the next counter-offer. A negotiation strategy is the determination of overall direction of bargaining tactics. Therefore, a negotiation strategy may contain multiple types of tactic for related criteria.
Negotiation tactics are short-term, adaptive moves designed to pursue higher-level negotiation strategies, which in turn provide stability, continuity and direction for tactical behaviors (Roy et al., 2009). Negotiation strategies are categorized into distributive and integrative. The distributive bargaining strategy applies a zero-sum game where individual gain is emphasized. The interests of negotiation are always opposed with opponent. On the other hand, the integrative bargaining strategy encourages a win-win negotiation or joint-gain. Since negotiators under this strategy have congruent interests and willing to cooperate, thus, the long-term relationship is introduced. Resource federation in grid is obviously a scenario of integrative bargaining. VO participants always search and perform the solutions that meet the goals and objectives of all. This idea is also applied in the proposed negotiation framework in this research.
However, integrative negotiation is difficult to solve compare to distributive negotiation due to several factors. For example, a terrible history of previous relationship worsens the cooperation magnitude. Some cognitive biases create perception and belief that a criterion is unable to be resolved in integrative mode. Besides, mixed-motive (mixture of distributive and integrative concerns on negotiation criteria) also resists the success of an integrative negotiation. Some participants are not willing to compromise with certain negotiation criteria. As a result, agreement will be terminated or never achieve with incomplete negotiation outcome. These challenges should be considered during the design of an integrative negotiation framework.
Perform automated negotiation between two agents involves several steps. Those steps included policy and requirement specifications, relationship building between participants with identification exchanged, information gathering with the opponent’s needs, opponent’s behavior and background analysis, bidding process, closing the deal, and lastly enforce the agreement. Applying autonomous agent in automated negotiation is the process of designing software agents to perform the mentioned functionalities on behalf of its owners. Challenges arise on how an agent can obtain the owner’s preferences precisely. A hierarchical-based policy representation technique is adopted in the research to address this issue.
The conventional automated negotiation processes are separated into three phases, namely pre-negotiation, conduct of negotiation and post-negotiation. This is a slightly simplified version of the previous steps. The pre-negotiation is the start of the overall process. The preparation for bargaining such as determination of the criteria to be negotiated and assigning the appropriate values for the proposal are arranged. Second phase is making trade-off in order to satisfy both participants. Third phase is post-negotiation which involves negotiation resolution. The process of negotiation resolution included the agreement reconciliation and enforcement.
The main challenges of implementing automated negotiation with intelligent agents included:
To securely delegate the agent with owner’s authority,
To clearly clarify different set of goals and expectations through negotiation tactics and strategies,
To accurately represent owner’s preferences into agent’s belief,
To cultivate positive relationships between agents by understanding different needs,
To avoid any negative elements that could limit spaces of toleration, and
To frequently explore beyond the obvious solution.
2.4 Conflict resolution in automated negotiation
Nowadays, the grid resource federation is more complicated compare to early solutions. However, the adoption of WS standards for latest OGSA provides arbitrary services for discovering and acquisition of heterogeneous resources easily. This requires higher flexibility in resource specification because the diverse policies used to control the access of resources become gradually complex. The conventional policy matching is unable to find a resource easily because the constraints imposed by different policies hinder the process. Due to this difficulty, a negotiation mechanism is needed. The resource federation which composes of multiple synchronous requests to different participants in a VO requested an agile and flexible yet organized method to solve the problem. Achieve satisfaction of different participants at the same time creates a challenge in grid resource federation. In this research, a Select, Match, Negotiate and Expand (SMNE) protocol is illustrated to depict the capability of conflict resolution of intelligent agent in a negotiation platform.
As mentioned earlier, the post-negotiation which involves conflict resolution and agreement enforcement plays an important role to ensure the success of a deal. Various types of distributed resources are attached with corresponding resource usage policies. Each policy will further detail into different criteria. Frequently, one common criterion in all policies may affect each others. For example, the allocation for several types of resources must be allocated in the same period. Conflicts between VO participants may happen when local administrative policies for each participant contradict each others. The resource federation is unable to proceed without a good mechanism to resolve the conflicts.
Compromising in either participant for the requested criteria can help in solving the disputes or conflicts. The compromise can either performed by the VO administrator or local administrator. This action is necessary to cultivate positive relationships between VO participants and also to avoid any negative elements that could limit spaces of toleration in the future. Besides, few circumstances may also require compromising from either participant:
Limited participants during the resource federation because the possibility in locating the best participant is rare.
Maximizes the satisfaction for both participants (VO and local administrators) in an integrative negotiation since local domain emphasizes on self-interested resource utilization while global resource utilization is important for a VO.
Certain candidates are targeted as preferable VO participants during the resource federation, thus, compromising during policy reconciliation brings higher chances for a satisfied federation.
Policy reconciliation is categorized into conflict resolution technique in automated negotiation. Several conflict resolution techniques have been studied. Persuader system (Sycara, 1989) was developed to model adversarial conflict resolution in the domain of labor relations. Persuader system adopts both case-based reasoning (CBR) and multi-attribute utility theory (MAUT) to mediate conflicts between participants. Several intelligent agents negotiate on multi-criteria iteratively. A mediator agent is responsible to solve the conflicts between the company and union according to the social reasoning model. Iterative and incremental modification of agents’ belief through counter-proposal is used to narrow down the differences between agents’ goal. This system allows an agent to influence and change the opponent’s belief incrementally. However, agent’s belief may not be the same and could be unique in resource federation practically. A distributed system like grid computing has never centralized the configuration.
Besides applying reasoning ability in conflict resolution, several heuristic approaches have been proposed as well. For example, Mailler et al., 2004 applied hill climbing algorithm in Scalable Protocol for Anytime Mediation (SPAM) to identify the over-constrained criteria, subsequently, recommend an appropriate solution. Kraus proposed a strategic negotiation model for conflict resolution (Kraus, 2006) in multi-agent negotiation platform. The negotiation model offers sequencing and re-submission of new counter-offer when the offer rejected by either participant in the negotiation. Rahwan et al. proposed an automated negotiation with agent argumentation-based negotiation protocol (Rahwan et al., 2004). The proposed protocol allows agents to exchange additional information, or to “argue” and potentially influences others about its beliefs and mental attitudes during the bargaining. Furthermore, Barbuceanu and Lo, 2000 also developed a constraint optimization/relaxation and information exchanged negotiation engine to solve the conflicts in constraint satisfaction problems.
The Montreal taxonomy (Ströbel and Weinhardt, 2003) was used to classify and evaluate the negotiation protocols. In Ströbel and Weinhardt research, a rule-driven selection technique was proposed for conflicts resolution. A tie-breaking rule is applied to complement the resolution process. The tie-breaking rule will define how the selected conflicts are being resolved. Conflicts are forwarded and resolved by intelligent agents if resolution and tie-breaking rules unable to settle the problems. Conflicts in Montreal taxonomy are solved by using a fixed set of pre-defined rules. This is impractical for grid domain but the rules mentioned in the paper (Ströbel and Weinhardt, 2003) can refer as a guide in evaluating negotiation protocol.
Cheng et al. also presented a multi-agent negotiation framework with the comparison of performances between various machine learning methods (Cheng et al., 2005, 2006). In the proposed framework, the application of negotiation tactics and strategies during negotiation were demonstrated. Self-interested agents are applied to study the opponent’s behavior in this framework. Local performance of the agent is emphasized to investigate the possibility in applying autonomous agent in grid environment. This framework is extended with more variety of agents, negotiation tactics and strategies, and also a comparison of the behavior of agents in distributive and integrative negotiation environments (Cheng et al., 2010). Several modules such as policy management and conflict resolution are added to examine the agent performances in the multi-agent negotiation platform.
In section 2.2, several automated negotiation techniques are listed. The mentioned techniques can be categorized either into conflict resolution techniques which can resolve the conflict and dispute between multiple participants, or conflict avoidance techniques which do not provide conflict resolution or mediation ability. For example, Globus (Czajkowski et al., 1998), Condor (Litzkow et al., 1998), Legion (Grimsaw & Wulf, 1996), contract net protocol (Smith, 1980) and logic-based approach (Sadri et al., 2002) are categorized under conflict avoidance techniques. These techniques either do not provide or only grant low level of conflict resolution ability. Compromising between participants will not exist in conflict avoidance techniques but more likely an automated direct policy matching will be applied. The conflict avoidance techniques are unable to cultivate positive relationships during resource federation between agents by understanding different needs. With comparison to game theory (Binmore & Vulkan, 1999), constraint relaxation protocol (Barbuceanu & Lo, 2000), argumentation-based approach (Rahwan et al., 2004), web service approach (Paurobally et al., 2005) and Montreal taxonomy approach (Ströbel & Weinhardt, 2003), these techniques provide a more powerful mechanism in handling the conflict and dispute during the conduct of negotiation. Nevertheless, several improvements in the above techniques are needed in order to provide better policy reconciliation in the problem of grid resource federation.
Besides the mentioned approaches, authors also study the possibility of integrating several well-known conflicts resolution techniques adopted in human negotiation. According to Roy et al., 2009, several applicable techniques are adopted in solving the conflict and dispute for integrative negotiation. These techniques are listed below.
Expanding the pie adds extra negotiation resources (e.g. policy criteria) to the current policy to achieve goals for both agents through integrative negotiation. This technique is useful since both agents always spend their effort in understanding other’s needs. However, the resources to be expanded need to be determined carefully and not over-tiered than previous discussed policy. This method is chosen in the proposed SMNE protocol.
Logroll, trade off among the policy criteria so that each participant alternately achieves highly preferred outcome on a particular criterion. Problem in this technique is how to decide who has the authority to start the selection of the preferred criterion. If both agents have the same highly preferred issue, then conflict may arise again.
Applied nonspecific compensation allows an agent in obtaining its goals and pay off the other agent for accommodating its interests, where the compensation is not directly related to the substantive criteria being discussed. This technique requires the agent to know what is valuable to the other agent and how seriously the agent is inconvenienced due to the compromise. The distributive negotiation may happen once the compensation value is too demanding.
Lowered the compliance costs, an agent achieves its goals meanwhile other values are minimized if the agent agrees to go along. This technique requires the knowledge of the other agent’s actual needs and preferences. However, the solution spaces become restrictive because the criteria constraints are increased.
Generated bridge solution, is reformulation of the constraints and both agents disclose sufficient information to discover their interests and needs, thus, inventing alternatives that will satisfy both. However, the outcome of reformulation does not always remedy all concerns and both agents require compromising on the results. Furthermore, agents may also disclose irrelevant or private information without proper policy management.
Other methods like brainstorming, nominal groups and surveys, will only be applied with the aid from a group of other agents. This requires extensive collaboration between the autonomous agents. This may not be applicable in resource federation because each agent in a VO is owned by different owners where each local administrator may vary in their opinions. Consensus may not easily achieve without a proper centralized management in the dynamic VO environment.
The application of intelligent agent allows the automation of negotiation process and exchange of messages in resource federation. The autonomous and flexible behaviors of the intelligent agent allow the owners to easily delegate his authority, preferences, goals and expectations onto the corresponding agent in an organized format. Several components are designed in order to develop an agent negotiation framework. For example, an automated negotiation protocol which defines actors, roles and negotiation phases; an agent communication protocol to define the agent’s goals, strategies, tactics and criteria; a negotiation policy language to define normative understanding rules; and a negotiation policy taxonomy to identify different types of policy in negotiation environment.
From the findings of literature review, there is definitely no universal approach for automated negotiation which can solve all problems. Rather, a set of approaches have been proposed, each relied on different assumptions and constraints on the negotiation environment and the participants involved. An approach must be designed and evaluated from different perspectives (e.g. Montreal taxonomy) in order to verify the applicability as a problem solution. From the analysis, WS-based of resource description is suitable to be applied for user interaction. A flexible and robust negotiation protocol with conflict resolution capability is proposed to solve the grid resource federation. Several challenges such as policy representation, policy selection and autonomous negotiation are the important aspects considered in this chapter. An automated negotiation protocol with the adoption of intelligent agents is illustrated in the following section to solve the problem of resource federation.
3. Multi-agent negotiation platform
A comprehensive study and analysis on the available agent negotiation techniques has been carried out in the Section 2. An agent negotiation framework in grid resource federation with the consideration of challenges mentioned in Section 2.3.1 is proposed. A Java Agent Development Extension Framework (JADEX) (Braubach et al., 2006) is chosen as the agent development tool in this research. JADEX is applied because of the outstanding embedded reasoning engine – Belief-Desire-Intention (BDI) model (Rao & Georgeff, 1995). The concept of BDI is applied in performing decision making according to human mental attitudes. This concept is adopted by the intelligent agent since the agent is required to perform negotiation according to administrator preference. Besides BDI reasoning engine, JADEX also provides several middleware with standard protocol such as communication infrastructure and management facilities. For example, JADEX communication messages follow standard of FIPA-ACL (Foundation for Intelligent Physical Agents – Agent Communication Language) (FIPA, 2002). FIPA promotes agent-based technology and the interoperability of its standards with other technologies. It provides the specifications for a standard agent language, ontology’s structuring for the semantic content of messages and an abstract agency model.
The JADEX agents are written using two types of language – XML and Java. The XML is used to express the agent definition file (ADF). The content of an ADF consists of the agent●s beliefs, goals, plans headers, triggering events and other agent instantiation properties. Each ADF binds with a corresponding logical structure written in Java language. Those logical structures define the actual behavior of an agent in handling the incoming action requests. JADEX provides a control centre to create multiple containers to hold different types of agents. In actual implementation, the main container resides on the local host. It runs the platform●s Remote Method Invocation (RMI) server which allows agents from diverse containers on distributed platforms (resources) to utilize the RMI protocol to communicate. This can be used to simulate resource federation with distributed resources from different VOs.
In order to solve the problems of resource federation in a dynamic grid environment, a one-to-many resource selection protocol with one-to-one policy reconciliation using automated negotiation has been proposed. The proposed resource federation model is simulated and tested in a multi-agent platform using JADEX. Several machines are interconnected to represent the distributed grid topology. Each of the machines is deployed with one or more intelligent agents in representing diverse local site. Each site is owned by a different administrator with corresponding local resources. The accessibility of the resources is stated clearly in the resource usage policy which is drafted by the local administrator. Requirement and specification of resource sharing are listed in each policy criteria. A VO initiator will be randomly chosen from the list of agents in order to start the simulation of resource federation. Several scenarios are prepared to examine the proposed agent negotiation and conflict resolution protocol.
In this research, an automated negotiation framework with the integration of resource selection, policy negotiation and reconciliation, and multi-agent platform has been illustrated. According to several earlier experimental results (Cheng et al., 2005, 2006, 2010), the proposed integration method, namely Select, Match, Negotiate and Expand (SMNE) protocol, was well performed with different experimental data which included various quantitative and qualitative policy criteria. Therefore, further investigation is being conducted to examine the performance of the SMNE protocol.
3.1 Select, Match, Negotiate and Expand (SMNE) protocol
As shown in Fig. 4, the SMNE protocol mainly performs four major tasks:
Selection: The first task is the resource selection. A one-to-many policy evaluation is performed to differentiate policies from different participants. A list of potential participants is generated with the comparison of non-negotiable criteria from the policies for further one-to-one negotiation.
Matching: The second task is to find out the negotiable criteria. Negotiable criteria are determined, ranked and weight by intelligent agent according to pre-assigned administrator’s preferences for further negotiation. A Multi-Criteria Analysis (MCA) method is applied during the policy evaluation.
Negotiation: Iterative bargaining is performed based on the negotiable criteria (as stated in the resource usage policies) in achieving a mutual acceptance between the local and VO administrators. Several negotiation strategies and tactics can be applied at this stage to increase negotiation’s outcome satisfaction.
Expansion: This stage is only performed if negotiation has failed to reach a mutual acceptance. Compromise is needed in order to expand the spaces of negotiation. Some constraints are resolved to increase the satisfaction of both intelligent agents during a conflict or dispute.
For further explanation, the SMNE protocol is always initiated by the VO initiator (administrator) during the selection of participants. For automated resource federation with intelligent agents, the first challenge always faced by the developer is to securely delegate the agent with owner’s authority. Security and trust management are adopted to authenticate the identity of VO participants and resolve different security conditions which apply to various resources. Several researches have been conducted, such as Djordjevic & Dimitrakos, 2004 and Naqvi & Mori, 2009 on security and trust management model. Grid security may not limit to the encryption of data during file transfer, tamper-proof to the intrusion by unauthorized intruders, delegation of authority for software communication, it also emphasizes on how to build up relationship in a trust management model. In an open grid environment, agents are requested to interact with other unfamiliar agents. Therefore, several security models such as public key infrastructure, access control list, role-based authentication and digital certificate authentication have been proposed and examined. These models may use centralized or decentralized repository to verify the identity of an agent. Either model can be adopted during the resource selection in the proposed SMNE protocol. Administrators feel more secure and comfortable in delegating their authority on the agents after applying the security model. This can avoid the unintended actions performed by the agents without a proper control with the model.
At the meantime of verification of the participant’s identity, an administrator may also need to define criteria value, preferences, goals and other important parameters such as negotiation strategies, tactics and threshold values for bargaining. This will be the second challenge during the development process. As shown in Fig. 1, a hierarchical-based policy representation technique is adopted to represent the owner’s preferences in resource usage policies. Owner can easily show his preferences on each criterion by using ranking and weighting mechanism. Rank Order Centroid (ROC), Analytic Hierarchy Process (AHP), or Simple Multi-attribute Rating Technique (SMART) can be applied to assign weight respectively (Cheng et al., 2010). Besides, a belief-based architecture is also adopted to represent the owner’s preferences into the agent’s belief. JADEX (Braubach et al., 2006) Agents incorporate the Belief-Desire-Intention (BDI) reasoning engine to mimic human actions and attitudes in decision making. Four types of goal (perform, achieve, query, and maintain) are introduced into the agent’s lifecycle as the objectives to be achieved. Plans or actions are inter-correlated with corresponding goals to perform tasks being assigned by administrator. The BDI model allows the agent to represent different conditions and states easily.
Furthermore, a negotiable criterion must have a range of valid choices which can be used in bargaining. A minimum acceptable value, Vmin, is accompanied by another optimal maximum value, Vmax in providing the choices (as shown in Fig. 3). Negotiation strategies and tactics are adopted to determine the value to be offered in each criterion during the offer and counter-offer process. The selection of negotiation strategy leads to the determination of overall direction of negotiation tactics. The common negotiation tactics included time-dependent, resource-dependent, behavior-dependent and relation-dependent (Cheng et al., 2005). Each tactic is modeled with a corresponding mathematical function to determine the next value during the counter-offer process. Meantime, a negotiation strategy is selected from the group of artificial intelligence method (e.g. fuzzy logic, neural network), heuristic method (e.g. reinforcement learning, aggressive, passive), relationship model (e.g. relation-based) and standard model (e.g. linearly increment, linearly decrement) (Cheng et al. 2006, 2010).
In SMNE protocol, a relationship model is adopted to determine the value to be offered during negotiation, namely Relation-Based Negotiation (RBN) strategy. The RBN strategy allows the agent to compromise according to the accumulated credibility from the past (Cheng et al. 2010). Better offer will be proposed in each attempt when both agents have more successful collaboration occurred before. The RBN is able to cultivate positive relationship between agents because agents more likely to share their resources in an integrative mode. Bad performance will be punished with credibility deduction where sincere collaboration will be rewarded with high credibility. This recalls the agents to always understand opponent’s needs and avoid self-interested behavior.
After the selection of participants, the matching and evaluation of the proposals are performed by the agent. SMNE applies Multi-Criteria Analysis (MCA) method to evaluate and rank the received proposals. ELECTRE III (Cheng et al., 2010) is chosen after the comparison between various MCA and Constraint Satisfaction Problem (CSP) (Tsang, 1993) methods. Both methods are able to solve the problems pertaining to multi-criteria but MCA outperforms CSP in providing higher flexibility and modularity for administrator to characterize his preferences during proposal evaluation. Various methods can be applied in different modules (weighting, thresholding, utility aggregation) in order to fulfil different MCA requirements. Since MCA and CSP methods have the corresponding features to easily adopt administrator’s preferences, authors also further compared the capability of MCA and CSP in performing criterion value compensation. The calculation of compensation needed was an attempt to quantify the credibility of opponent and also refer as a guide for the agent to perform next counter-offer in RBN. A comparison between RBN with conflict resolution and direct negotiate with new opponent during conflict is conducted in order to investigate the satisfaction of VO administrator in performing resource federation. The experiment is performed to examine the satisfaction of the proposed SMNE with the existence of different numbers of participants. The outcome can further explain the most suitable situation to apply conflict resolution in resource federation.
From the complexity aspect, MCA requires more computation power during pre-negotiation for weighting and thresholding. In this method, administrator also needs to provide more details on his preferences into the agent’s belief. Meanwhile, CSP consumes more computation in the process of solution searching (conduct of negotiation) when the amount of criteria gets vast. The complexity of NP-complete in CSP urges for a better heuristic solution in policy negotiation. From negotiation aspect, CSP is more suitable for one-to-one negotiation compares to MCA. Most of the time, proposals from other participants will not be directly considered during CSP. The CSP is useful in performing a direct negotiation between two participants, where MCA takes a different approach to collect multiple concurrent proposals followed by an evaluation and ranking process. A one-to-many negotiation approach is adopted with MCA. Therefore, MCA is determined as more suitable solution for multi-criteria proposal evaluation.
Additionally, ELECTREE III applies pseudo-criteria with fuzzy outranking relation for proposal evaluation (Cheng et al., 2010). This feature allows ELECTRE III to deal with inaccurate, imprecise and uncertain data, which is applicable to the scenario of resource federation in dynamic grid environment. However, the tedious step of parameters configuration for threshold values, scoring and scaling functions requires further improvement.
From the generated list of participants, the proposal of highest order is chosen for further negotiation. Negotiation strategies and tactics are adopted at this stage for bargaining and trade-off. As mentioned earlier, RBN is adopted by SMNE protocol to cultivate positive relationship between agents. However, a bottleneck (conflict) may occur once both agents are unable to further compromise. As a solution, the agent can always seek for another participant from the list. But, this may not promise for a successful bargaining and possible lead to an exhaustion of time. In order to counteract this problem, the concept of Creative Negotiation (Billikopf, 2003) is proposed. Creative negotiation is only triggered in specific conditions. For example, once the agent discovers the opponent is unable to further provide a better offer (e.g. no or very small differences with the two continuous proposals from the same opponent), then one or more add-on criteria will be introduced into the bargaining to expand the negotiation spaces for conflict resolution (Cheng et al., 2010).
As listed in the Section 2.3.1, negotiation should always avoid any negative elements that could limit spaces of toleration. An autonomous agent should be design with the mechanism to frequently explore beyond the obvious solution. In SMNE protocol, agents always expand the spaces of negotiation (pie) with the concept of creative negotiation. A constraint is resolved with the compensation of additional criteria which may direct or indirect affect the unsatisfied criterion. For example, the VO administrator requests 1MB/sec of network transfer rate from a network service provider without the consideration of stability. Without the promise of stability, the downtime of network can seriously affect the performances. However, due to certain reasons the network service provider is unable to provide the requested speed but a different offer with additional consideration can be proposed. The network service provider can counter-offer the VO administrator with a minimum 512Kb/sec of network transfer rate and also a better quality of service with 99.9% of network availability during resource federation. The newly proposed criterion, namely network availability is generated to compensate the insufficient network transfer rate. An important concern is raised out through the bargaining and compensation process, thus, credibility can be awarded to the network service provider in rewarding the sincere integrative collaboration. Of course, a threshold value, T, is set to avoid the negotiation outcome deviate seriously from the initial requests. Further explanation of creative negotiation in SMNE protocol is discussed in the paper (Cheng et al., 2010).
4. Experimental results and discussion
A multi-agent negotiation platform is developed by using JADEX in order to simulate the grid resource federation. Several distributed grid topology is simulated with a group of interconnected machines. Agents are randomly deployed into each machine to represent the local administrators. Resource usage policies are also randomly assigned with different qualitative and quantitative values in order to represent diverse administrator’s behavior in sharing their resources. Satisfaction and Time factors are tested in the experiments.
Satisfaction factor indicates the willingness of the agent to accept an offer during a negotiation. In the experiments, the differentiation between the final offered values from the opponent with agent’s estimated (comfortable) value is calculated (1). Larger positive percentage indicates more comfortable or higher willingness of an agent to accept an offer, while 0% specifies the offer is in the expectation, and lower negative percentage indicates a higher level of dissatisfaction of an offer. In the experiments, the satisfaction of VO initiator (administrator) is captured because the VO initiator may need to coordinate and negotiate with different agents at the same time.
Time factor shows how fast the VO initiator (agent) can achieve a mutual acceptance with an agent from the list of participants. Time calculated including proposals evaluation from a given number of participants and the overall negotiation process until a successful deal is achieved (2).
Experiments have repeated with different numbers of participants (agents), range from 10 – 200 participants. This intends to simulate a dynamic VO with different structures. Besides, two different types of method are compared, namely negotiation only method (NO) and conflict resolution method (CR). In negotiation method, if both agent failed to achieve a consensus, then the VO initiator will seek for another agent in the list. This action is repeated until the agent has successfully striking a deal. This method is also representing the conventoinal automated negotiation method. On the other hand, conflict resolution method will proceed with other solutions in resolving the conflict. As discussed in the proposed SMNE protocol, creative negotiation (Cheng et al., 2010) is applied in our experiments.
An experiment is conducted to investigate the satisfaction level between NO and CR with different numbers of participants. As mentioned earlier in Section 2.4, authors believed CR can outperform NO in staisfaction factor once the number of participants is small during the resource federation. Besides, the most suitable circumstances to apply CR compare to NO is also studied in order to provide a guide to VO administrator for future reference during participant selection. According to Fig. 5, experimental results show that:
Agents achieve higher satisfaction with more participants in a VO.
CR only outperforms NO when the number of participants is limited (<90 participants).
CR can achieve better satisfaction when NO finds difficulty in striking a deal (number of participants = 20, 60, 140).
None of the method can absolutely outperform the other when the number of participants is getting larger.
With the same experiment setup, overall time for the proposals evaluation, negotiation until striking a deal has been captured. This experiment is performed to examine the capability of the NO and CR methods in striking a deal in reasonable time frame. Meanwhile, authors also intended to evaluate the additional time and effort spent in locating new participant under the NO method. Fig. 6 shows the following findings:
A gradually increment of processing time for both methods, NO and CR.
CR in average takes shorter time in striking a deal compare to NO.
NO always takes longer time in striking a deal when most of the participants is unable to compromise (number of participants = 20, 60, 140).
CR is a more stable and predictive model compare to NO.
As shown in both figures (Fig. 5 and Fig. 6), SMNE protocol is useful especially when the VO has limited participants. Level of satisfaction in SMNE protocol can be maintained meanwhile the conventional automated negotiation method is struggling for a successful deal with multiple participants when none of them can further compromise. As a conclusion, a faster and time-predictable method is performed by SMNE protocol. This has proved the previous arguments on the applicability of conflict resolution method in automated agent negotiation as stated in Section 2.4.
5. Conclusion and future works
In this chapter, a conflict resolution model for multi-agent negotiation during grid resource federation is proposed and examined. Experimental results are shown that the conflict resolution method outperforms conventional negotiation method especially when VO has fewer participants. Besides, several automated agent negotiation approaches are compared and discussed in this review. A conflict resolution method, namely creative negotiation is successfully integrated into the SMNE protocol. Furthermore, several possible challenges for the implementation of SMNE protocol with intelligent agent are listed for further discussion.
Automation of several agent configurations such as negotiation strategies and tactics alteration in different situations, optimal parameters and threshold values assignment, are still opened issues for further improvement. Deployment of the proposed SMNE protocol into the real grid environment with several uncertainties such as network latency, system breakdown and hardware failure are yet to be analyzed. These issues remained as future work.