Theoretical and Computation Basis for CATNETS - Annual Report Year 3

Bayreuther Arbeitspapiere zur Wirtschaftsinformatik Lehrstuhl für Wirtschaftsinformatik Information Systems Management Bayreuth Reports on Information Systems Management No. 23 2007 Daniel Veit, Georg Buss (University of Mannheim), Björn Schnizler, Dirk Neumann (University of Karlsruhe), Werner Streitberger, Torsten Eymann (University of Bayreuth) Theoretical and Computational Basis for CATNETS - Annual Report Year 3 ISSN 1864-9300 Die Arbeitspapiere des Lehrstuhls für Wirtschaftsinformatik dienen der Darstellung vorläufiger Ergebnisse, die i. d. R. noch für spätere Veröffentlichungen überarbeitet werden. Die Autoren sind deshalb für kritische Hinweise dankbar. The Bayreuth Reports on Information Systems Management comprise preliminary results which will usually be revised for subsequent publications. Critical comments would be appreciated by the authors. Alle Rechte vorbehalten. Insbesondere die der Übersetzung, des Nachdruckes, des Vortrags, der Entnahme von Abbildungen und Tabellen – auch bei nur auszugsweiser Verwertung. All rights reserved. No part of this report may be reproduced by any means, or translated. Authors: Information Systems and Management Working Paper Series Edited by: Prof. Dr. Torsten Eymann Managing Assistant and Contact: Raimund Matros Universität Bayreuth Lehrstuhl für Wirtschaftsinformatik (BWL VII) Prof. Dr. Torsten Eymann Universitätsstrasse 30 95447 Bayreuth Germany Email: [email protected] ISSN Daniel Veit, Georg Buss (University of Mannheim), Björn Schnizler, Dirk Neumann (University of Karlsruhe), Werner Streitberger, Torsten Eymann (University of Bayreuth) 1864-9300 IST-FP6-003769 CATNETS Y3 Report WP 1: Theoretical and Computational Basis Contractual Date of Delivery to the CEC: 31. August 2007 Actual Date of Delivery to the CEC: 30. September 2007 Author(s): Daniel Veit, Georg Buss (University of Mannheim) Bj¨orn Schnizler, Dirk Neumann (University of Karlsruhe) Werner Streitberger, Torsten Eymann (University of Bayreuth) Workpackage: WP 1 Theoretical and Computational Basis Est. person months: 19 Security: public Nature: submitted version Version: 1.0 Total number of pages: 50 Abstract: This report covers the results of WP1 in Y2, Y3 and hence comprises mainly the results from T1.4 and T1.5. Keywords (optional): Decentralized Market Mechanisms, Centralized Market Mechanisms, Catallaxy, Market Engineering, Simulator Integration, Prototype Integration CATNETS Consortium This document is part of a research project partially funded by the IST Programme of the Commission of the European Communities as project number IST-FP6-003769. The partners in this project are: LS Wirtschaftsinformatik (BWL VII) / University of Bayreuth (coordinator, Germany), Arquitectura de Computadors / Universitat Politecnica de Catalunya (Spain), Information Management and Systems / University of Karlsruhe (TH) (Germany), Dipartimento di Economia / Universit´a delle marche Ancona (Italy), School of Computer Science and the Welsh eScience Centre / University of Cardiff (United Kingdom), Automated Reasoning Systems Division / ITC-irst Trento (Italy), Chair of Business Administration and Information Systems - E-Business and E-Government / University of Mannheim (Germany). University of Bayreuth LS Wirtschaftsinformatik (BWL VII) 95440 Bayreuth Germany Tel: +49 921 55-2807, Fax: +49 921 55-2816 Contactperson: Torsten Eymann E-mail: [email protected] Universitat Politecnica de Catalunya Arquitectura de Computadors Jordi Girona, 1-3 08034 Barcelona Spain Tel: +34 93 4016882, Fax: +34 93 4017055 Contactperson: Felix Freitag E-mail: [email protected] University of Karlsruhe Institute for Information Management and Systems Englerstr. 14 76131 Karlsruhe Germany Tel: +49 721 608 8370, Fax: +49 721 608 8399 Contactperson: Christof Weinhardt E-mail: [email protected] Universit´ a delle marche Ancona Dipartimento di Economia Piazzale Martelli 8 60121 Ancona Italy Tel: 39-071220.7088 , Fax: +39-071220.7102 Contactperson: Mauro Gallegati E-mail: [email protected] University of Cardiff School of Computer Science and the Welsh eScience Centre University of Caradiff, Wales Cardiff CF24 3AA, UK United Kingdom Tel: +44 (0)2920 875542, Fax: +44 (0)2920 874598 Contactperson: Omer F. Rana E-mail: [email protected]f.ac.uk ITC-irst Trento Automated Reasoning Systems Division Via Sommarive, 18 38050 Povo - Trento Italy Tel: +39 0461 314 314, Fax: +39 0461 302 040 Contactperson: Floriano Zini E-mail: [email protected] University of Mannheim Chair of Business Administration and Information Systems - E-Business and E-Government - L9, 1-2 68131 Mannheim Germany Tel: +49 621 181 3321, Fax: +49 621 181 3310 Contactperson: Daniel Veit E-mail: [email protected] Contents 1 Introduction 3 2 Self-Organization in Computing Systems - Putting CATNETS into a Greater Perspective 5 2.1 Introduction to Self-Organization . ..................... 5 2.2 Infrastructural Spheres of Self-Organizing Computing . . . . ....... 6 2.3 The Open Service Infrastructure . ..................... 7 2.4 About the Necessity to Create an Open SOC Policies Infrastructure . . . . 8 3 Formal Description of Mechanisms 10 3.1 Centralized Mechanisms . . . . . ..................... 10 3.2 The Catallaxy as an Alternative Decentralized Approach . . ....... 11 3.2.1 Setup and Variables Definition . . . . . .............. 13 3.2.2 The Negotiation Strategy . ..................... 14 3.2.3 Gossip Learning . . . . . ..................... 17 3.2.4 The Learning Algorithm . ..................... 17 4 Bidding Issues 20 4.1 What Does an Agent Bid? . . . . ..................... 20 4.1.1 Notation . . ............................ 20 4.1.2 Valuation Generation . . . ..................... 21 4.1.3 Calibration of the Valuation Generator . .............. 23 4.2 When Does an Agent Bid? . . . . ..................... 24 4.2.1 Complex Service Agent . ..................... 24 4.2.2 Basic Service Agent . . . ..................... 24 4.2.3 Resource Service Agent . ..................... 27 4.3 Summary . . ................................ 28 5 Integration of Mechanisms into Simulator 29 5.1 Integration of the Auction Mechanisms . . . . .............. 29 5.1.1 Implementation of the Markets . . . . . .............. 29 5.1.2 Integration into OptorSim ..................... 33 5.2 Decentralized Mechanisms (Catallaxy) . . . . . .............. 35 1 CONTENTS 2 5.2.1 Implementation of the Markets . . . . . .............. 35 5.2.2 Integration into OptorSim ..................... 38 5.3 Simulation Results . ............................ 40 6 Relations to other WPs 43 6.1 WP2..................................... 43 6.2 WP3..................................... 43 6.3 WP4..................................... 44 7 Summary 45 7.1 Review ................................... 45 7.2 Content to Y3 ................................ 46 7.3 Outlook . . . ................................ 47 Bibliography 47 Chapter 1 Introduction The primary target of the CATNETS project is the quantitative comparison between the technical and economic efficiency of market-based resource allocation mechanisms in application layer networks such as Grids. Here, two fundamentally different approaches are compared. A centralized – auction-based – market mechanism and a decentralized – Catallaxy-based – market mechanism. After the reorganization (following the Y1 review) this endeavor has been approached in the following way: •Workpackage 1 (Theoretical and Computational Basis): The target of this workpackage is the definition of market mechanisms for the centralized and the decentralized case. Therefore, software components have to be identified (T1.1), market requirements have to be analyzed (T1.2) and an architecture for services and ALNs has to be designed (T1.3). Finally a specification for bidding and interaction issues has to be carried out (T1.4). A specification and analysis of the market mechanisms concludes WP1. •Workpackage 2 (Simulation Framework): The core of this workpackage is the implementation of a simulator framework integrating both, the centralized and the decentralized market mechanism. The goal is to compare the outcome of the application of both mechanisms quantitatively. •Workpackage 3 (Proof-of-Concept Applications): In parallel to WP2 this workpackage focuses on the implementation of the designed decentralized market mechanisms into a prototypical ALN-middleware software. Quantitative evaluations are carried out by running experiments with this platform. •Workpackage 4 (Performance Evaluation): The aim of this WP is the identification and design of metrics in order to measure the outcome of WP2 and WP3. Here, a metrics framework is designed in order to enable the measurement of the quality of allocation results in using an economic scale. 3 CHAPTER 1. INTRODUCTION 4 •Workpackage 5 (Management): This workpackage is designed to carry out project management and dissemination. This report covers the results of WP1 in Y2, Y3 and hence comprises mainly the results from T1.4 and T1.5. The remainder of this report is structured as follows: Chapter 2 illustrates research questions of the CATNETS project in the context of self-organizing systems and draws a vision towards future research topics. In the following, chapter 3 focuses on the description of the introduced market mechanisms. In Section 3.1 the properties of the centralized market mechanisms, which have been defined in Y1 report [SNV+05b] are briefly described. Section 3.2 provides a formal description of the decentralized allocation mechanisms. The bidding issues, presented in Chapter 4, elaborate different scenarios connecting the service and resource market. Advantages and disadvantages of these scenarios are compared to enable a comparison of the centralized and decentralized market mechanism. In Chapter 5 the integration of the mechanisms into the OptorSim simulator is outlined and links to WP2 are set. Therein, overall simulation results are provided. Chapter 6 relates Workpackage 1 to the other workpackages. Finally, Chapter 7 provides a summary of the work that was done in workpackage 1. Chapter 2 Self-Organization in Computing Systems - Putting CATNETS into a Greater Perspective 2.1 Introduction to Self-Organization The vision of Self-Organization in Computing Systems and Networks has gained significant interest in the last years, and even was labeled with a popular buzzword: Autonomic Computing [KC03] describes a concept of self-organizing information technology, where the functionality of the computing system is an emergent feature of the capabilities and actions of the components. Without any centralized controller, this system is capable of configuring, healing, organizing and protecting itself (the so-called CHOP properties). In contrast, classical IT control involves a centralized controller instance with global knowledge about the current status of the computing system, and a detailed regulation mechanism to ’heal’ deviations from a defined ’normal’ status. Centralized computation is said to be not that flexible in terms of scalability and adaptability. Autonomic Computing uses a biological paradigm as a design and control metaphor, the autonomic nervous system. The core CHOP properties of the Autonomic Computing concept are intended to be an electronic realization of the respective mechanisms of the human body. Self-organization can be found in other parts of our natural environment as well, e.g. biological evolution, social group behavior, market dynamics phenomena and other complex adaptive systems. Autonomics refers to our own human neural system, Catallaxy [ESMP03] to self-organizing markets in Economics, Stigmergy to coordination without communication in insect colonies. All these ideas have in common that the solution for growing complexity both in scale and semantics is decentralized control, that is based on local information and executed through local effects which build up to a system-wide emergent behavior. It is not surprising that projects labeled Autonomic Computing are thus manifold, coming from diverse backgrounds and academic habitats, and aiming at a variety 5 CHAPTER 3. FORMAL DESCRIPTION OF MECHANISMS 12 Figure 3.2: Decentralized Service Discovery decide on their own, and do not take the system state into account. In the Edgeworth process [Var94], economic subjects trade bilaterally with each other only if their utility is supposed to increase after the barter. In that case, the sum of all utilities increases after each successful barter; the final state is Pareto-optimal and has maximum system utility. A theoretical fundament how the concepts of dynamic market processes, heterogeneous agents and choice under incomplete information are linked, can be found in NeoAustrian Economics, in particular in Friedrich August von Hayeks Catallaxy concept [HBKC89]. Catallaxy describes a state of spontaneous order, which comes into existence by the community members communicating (bartering) with each other and thus achieving a community goal that no single user has planned for. The implementation of Catallaxy, described in this paper, uses efforts from both agent technology and economics, notably agent-based computational economics [Tes97]. Autonomous software agents negotiate with each other using an alternating offers protocol [Ros94] and adapt their negotiation strategies using feedback learning algorithms (evolutionary algorithms, numerical optimization e.g. Nelder/Meads simplex method [PT02], hybrid methods e.g. Brenners VID model [Bre02]). Ongoing communication by using price signaling leads to constant adaptation of the system as a whole and propagates changes in the scarcity of resources throughout the system. The resulting patterns are comparable to those witnessed in human market negotiation experiments [KR95][Pru81][Smi62]. CHAPTER 3. FORMAL DESCRIPTION OF MECHANISMS 13 3.2.1 Setup and Variables Definition While the notation for buyers, sellers and goods is the same as the one used in the centralized scenario, we need to add definitions for the decision-making process (the strategy) of the agents. The negotiation strategy described here is based on the AVALANCHE strategy [ESP98][Eym01]. The strategy consists of 5 basic parameters, which define the individual behavior (genotype) of each agent. For every tradable good there are two types of agents, buyers and sellers. Let agent k be a buyer and agent va seller of a tradable good. Let ikbe the number of negotiations that agent khas started and ivthe number of negotiations that agent vhas started. A genotype defines the behavior of the agents in the negotiation strategy. Let the genotype of agent ∗for ∗=k,v during his negotiation i∗be Gi∗ ∗∈[0; 1]5 with Gi∗ ∗=(Gi∗ ∗,1,...,G i∗ ∗,5)τ=(ai∗ ∗,s i∗ ∗,t i∗ ∗,b i∗ ∗,wi∗ ∗)τ where ai∗ ∗acquisitiveness si∗ ∗satisfaction ti∗ ∗priceStep bi∗ ∗priceNext wi∗ ∗weightMemory. Acquisitiveness defines the probability of sticking with the last offer made, and not to make an unilateral concession in the following negotiation step. The value interval is between 0 and 1, and will be challenged by a stochastic probe in every negotiation step. A value of 0.7 means a probability of 70% that the agent will not make a concession – a highly competitive strategy. An agent with acquisitiveness value 1.0 will never change his price and an agent with acquisitiveness value 0.0 will always make an unilateral concession. If the probe succeeds, a buyer agent will rise his offer, a seller agent will lower his price. The exact change of the bid value is defined by the concession level (priceStep). The concession level is represented by a percentage of the difference between the initial starting prices. A value of priceStep = 0.25 means a computation of the concession level as 1/4 of the first stated difference. If both opponents are homogenously negotiating and always concede, they meet each other on the half way in the third negotiation round under the assumption of no negotiation abortion. CHAPTER 3. FORMAL DESCRIPTION OF MECHANISMS 14 Obviously, with an acquisitiveness level set high, and a priceStep set low enough, the opponents might never reach an agreement. The satisfaction parameter determines if an agent will drop out from an ongoing negotiation. The more steps the negotiation takes, or the more excessive the partner’s offers are, the sooner the negotiation will be discontinued. Effectively, this parameter creates time pressure. Like for acquisitiveness, it does this by doing a stochastic probe against a set value between 0 and 1. A satisfaction value of 0.75 means, that the agent has a chance of 75% to continue the negotiation process. An agent with satisfaction = 0.0 will abort all negotiation at once and an agent with satisfaction = 1.0 will never abort. The last piece of the strategy is an expression of selfishness. Behind each successful negotiation lies a future opportunity for gaining more of the utility share, by negotiating harder. priceNext thus modifies the starting bid. A successful seller will increase his offer price, a successful bidder will start with a lower bid next time. For a viable strategy, the participants will have a close eye on what others deem to be the market price. If not, they risk being tagged as ”excessive” and their bids will fail the satisfaction probe. They thus weigh current price information and historic price information in a specified ratio weightMemory, balancing short-time price fluctuation and longer-term opportunities. At the beginning of the simulation the genes Gi∗ ∗,j for ∗=k,v and j∈{1,...,5}are distributed according to the probabilities: Ufo[mj−δj;mj+δj] Thereby, the constants mjand δjfor j∈{1,...,5}are defined so that [mj−δj;mj+ δj]⊂[0; 1] . Additionally, each agent ∗has the following variables: Mi∗ ∗:the market price, which is estimated by agent kduring his negotiation i∗. Pi∗ ∗:the price of the the last successful negotiation 1,2,...,i ∗of agent ∗. Oi∗ ∗:the last offer, which the negotiation opponent has made in negotiation number i∗the agent ∗ before the negotiation ended. pi∗ ∗:the number of stored plumages of agent ∗ direct after his negotiation i∗. 3.2.2 The Negotiation Strategy When agent kand agent vnegotiate, agent kis the buyer and agent vthe seller. The sequence (Pj)j∈IN 0⊂[0,∞[constitutes the offer in chronological order. The buyer always CHAPTER 3. FORMAL DESCRIPTION OF MECHANISMS 15 makes the first offer. This means, all offers P2m∀m∈IN 0 originate from the buyer and the offers P2m+1 ∀m∈IN 0 come from the seller, where m is the negotiation round. At the beginning of a negotiation the buyer kdetermines his initial price Kand his maximum price K: K=Mik k·(1 −bik k), K =Mik k The seller vdetermines his starting price Vand his minimum price V: V=Miv v·(1 + biv v),V=Miv v The buyer starts with the first bid: P0=K •First Case: K≥V Then voffers also P1=K and the negotiation will be closed successfully to the price P1. •Second Case: K< V Then voffers his initial price P1=V. Both agents determine now their steps δj∗ ∗for price concessions: δi∗ ∗=(V−K)·ti∗ ∗for ∗=k,v In the subsequent negotiation rounds, let A1,A 2,A 3,... and S1,S 2,S 3,... be stochastic independent random variables with the following binomial distributions: A2m=1with probability aik k 0with probability 1−aik k ∀m∈IN A2m+1 =1with probability aiv v 0with probability 1−aiv v ∀m∈IN S2m=1with probability sik k 0with probability 1−sik k ∀m∈IN S2m+1 =1with probability siv v 0with probability 1−siv v ∀m∈IN CHAPTER 3. FORMAL DESCRIPTION OF MECHANISMS 16 •Offer number 2m; it is the buyer’s kturn: If S2m=0and P2m−1≥P2(m−1)−1with m=1, then the buyer kcancels the negotiation. This means, Oik k=P2m−1and Oiv v=P2(m−1) . Otherwise, the buyer kmakes the following offer: P2m=min K,(P2(m−1) +δik k),P 2m−11−A2m · P2(m−1)A2m •Bid number 2m+1; it is the seller’s vturn: If S2m+1 =0and P2m≤P2(m−1), then the seller vcancels the negotiation. That means, Oiv v=P2mand Oik k=P2(m−1)+1 . Otherwise the seller vmakes the following offer: P2m+1 =min V , (P2(m−1)+1 −δiv v),P 2mA2m+1 · P2(m−1)1−A2m+1 The negotiation ends if either one of the agents cancels the negotiation or the negotiation ends successfully with Pj=Pj+1 for a j∈IN . In this case, it holds Oik k=Pj=Oiv v. With the end of a successful negotiation to the price Pjthe negotiation compute their estimated profit Πik k=Mik k−Pjrespectively Πiv v=Pj−Miv v. Additionally, both agents update after every negotiation their estimated market price using Mik+1 k=wik k·Oik k+(1−wik k)·Mik k respectively Miv+1 v=wiv v·Oiv v+(1−wiv v)·Miv v. This last step is independent of the success of a negotiation. CHAPTER 3. FORMAL DESCRIPTION OF MECHANISMS 17 3.2.3 Gossip Learning The learning concept used in this simulation is derived from so-called gossip learning. This means that the agents learn from received information about other transactions in the market. This information may not be accurate or complete, but serves as an indication about the gross direction of the market. In our implementation, this gossip information is created and broadcast by a successful agent, in analogy to issuing an ad-hoc information in stock market periodicals. Let nbe an agent and g1,...,g dthe tradable goods. The agent nhas finished his negotiation insuccessfully with an estimated profit of Πin n(g)for the good g∈{g1,...,g d}. Alearning step according to the learning algorithm (see subsection 3.2.4) is performed by agent nlast time at the end of his negotiation jk. This means Gjn+1 n=Gjn+2 n=···=Gin n. If agent nwith the negotiation numbers jn+1,j n+2,...,i n has successfully completed at least 10 negotiations for every good, he sends a Plumage (Gin n,Fin n) to all other agents of his type. Then, his updated fitness is Fin n, which is computed as follows: (a) For every good gj∈{g1,...,g d}the next profit value Π(gj)is determined: Let Π1(gj),...,Π10(gj) be the estimated profits of the last 10 successful negotiations of agent nfor the good gj. Then, the fitness is Fin n(gj)= 1 10Π1(gj)+···+Π 10(gj). (b) The updated fitness Fin nfinally is Fin n=1 dΠ(g1)+···+Π(gd). 3.2.4 The Learning Algorithm It is assumed that the agents show a cooperative behavior. This means, the agents report truthfully their learning information. CHAPTER 3. FORMAL DESCRIPTION OF MECHANISMS 18 After having received some gossip information message, the agent may modify his own strategy. The comparison of the own results with those of the strategy received may show that the other strategy superior to the own. In this case, the agent will try to cross both strategies to gain competitive advantage. In practice, out of a list of received genotype/performance-tuples, the agent will choose the best performing external genotype, and then mix, cross and mutate with his own genotype. Let be nan arbitrary agent at the end of his negotiation inand let be pin nthe number of plumages, the agent nhas stored directly after his negotiation in. The last learning step was performed by agent nafter his negotiation jk. Let be ein nthe number of negotiations, an agent nof the negotiation numbers jn+1,j n+2,...,i n has successfully finished. Let be p=1. If pin n<p or ein n<10 applies for agent nafter his negotiation in,nolearning step will be performed. This means, his genotype will not change: Gin+1 n=Gin n. Hence, if pin n≥pand ein n≥10 applies, the agent nperforms a learning step. The genotype of agent nchanges as follows: First, the stored plumage of agent nwith the highest fitness is selected. Let be Gf=(Gf,1,...,G f,5)τ=(af,s f,t f,b f,w f)τ the related genotype. Second, a crossover is performed. In doing so, a new genotype ˜ Gin+1 nis created, which contains a random mixture of genes of the genotypes Gin nand Gf. This process follows a mutation step third: Using the genotype ˜ Gin+1 nand changing its genes slightly will result in the genotype Gin+1 n. 3.2.4.1 Crossover Let be C1,...,C 5stochastic independent random variables with the following binomial distribution: Cj=1with probability 0,5 0with probability 0,5∀j∈{1,...,5} CHAPTER 3. FORMAL DESCRIPTION OF MECHANISMS 19 Then it is imperative ˜ Gin+1 n,j =(1−Cj)·Gin n,j +Cj·Gf,j ∀j∈{1,...,5}. 3.2.4.2 Mutation Let be M1,...,M 5,X 1,...,X 5stochastic independent random variables with the following distributions: Mj=1with probability 0,05 0with probability 0,05 ∀j∈{1,...,5} Xj∼N(0 ,1) ∀j∈{1,...,5} That means, Xjis ∀j∈{1,...,5}standard normal distributed. Then, it holds Gin+1 n,j =max0; min˜ Gin+1 n,j + Mj·(1 10Xj)mod(1);1 ∀j∈{1,...,5}. Chapter 4 Bidding Issues The purpose of this chapter is to clarify what and when an agent bids in the CATNETS scenario. What denotes the valuation and the reservation prices of agents, i.e. the maximal price which an agent is willing to pay for a service (resp. the minimum price an agent has for selling a service). When denotes the timing of bids, i.e. which event induces an agent to bid for a service. Both cases are different in the centralized and decentralized scenario. As such, it is important to find concepts that are applicable for both scenarios and, thus, make the results comparable. The chapter is structured as follows: Section 4.1 outlines the valuation generation of an agent, i.e. the procedure that determines the value of an agent’s bid. Section 4.2 describes the timing of the agent’s bids, i.e. when does an agent bid for a service. Finally, Section 4.3 summarizes the chapter. 4.1 What Does an Agent Bid? The following section describes what an agent bids, i.e. the valuation and reservation prices. For this, a generic function is developed that is applicable for both, the centralized and the decentralized case. The concept is applied for buyers and sellers in both markets, i.e. in the service market and in the resource market. 4.1.1 Notation Before the valuation generator is introduced, the general notation as denoted in table 4.1 is presented. The transaction object gdenotes the service for that a valuation is to be generated. 20 CHAPTER 4. BIDDING ISSUES 21 Transaction object g Valuation in period i V i Market price Mi Weight market price β Weighted Average wavi Weighted Memory wi Table 4.1: Notation for the valuation generation For instance, this could be a PDF creator in the service market. For each service, an agent has a valuation Vi(resp. reservation price) in each period i. This valuation denotes the maximum price, an agent is willing to bid for this particular service. The valuation generation is influenced by external factors such as the market price. In case such a market price exists for a transaction object in period i, it is denoted by Mi. For the centralized case, market prices may not exists in each period. In these cases, an approximated market price is used. The effect a market price has on the valuation generation is denoted by β. The lower this value is, the lesser the importance of old market prices. Finally, the weighted average waviand the weighted memory widenote noise parameters. 4.1.2 Valuation Generation Based upon the notation as introduced in the previous section, the valuation for a service gin time period i+1is calculated as follows: Vi+1(g)=βMi(g)+(1−β)wavi(g)+YX +Z(4.1) The valuation for the next period depends on the market price of the current period, the weighted average of former valuations, and some statistical noise. The weight of the market price and the weighted average depends on the static value β∈{0,1}which is predefined and fixed. From an implementation point-of-view, the variable βshould be definable via an external configuration file. It is to note, that the statistical noise functions are only applied in the centralized case. These functions are responsible for inserting exogenous factors (e.g. different dynamics, density scenarios) in the centralized simulation. In the decentralized case, this noise is generated by a genetic algorithm. However, this genetic algorithm will not be applied CHAPTER 4. BIDDING ISSUES 28 dle {A, B, C}would be higher than the sum of valuations of the resources {A},{B} and {C}. 4.3 Summary This section outlines bidding issues in the CATNETS scenario. A valuation generator is introduced that can be applied for buyers and sellers in both markets in order to determine values for their bids. The challenge of such a generator is to define a concept that is applicable for the centralized and the decentralized case and that leads to comparable outcomes. Chapter 5 Integration of Mechanisms into Simulator Subject to this chapter is the technical integration of the centralized and decentralized mechanisms into the simulator (Section 5.1 and Section 5.2). Here, a string interaction with WP2 will be carried out in order to avoid overlaps in documentations. Furthermore in Section 5.3 an insight into the results of the comparison of the centralized to the decentralized mechanism is given. For an in depth analysis the reader is referred to [BCC+07]. 5.1 Integration of the Auction Mechanisms The objective of this section is to describe the implementation of the auction mechanisms (Section 5.1.1) and their integration into OptorSim (Section 5.1.2). 5.1.1 Implementation of the Markets In the following, the implementation of the service market and the resource market is described. Both market mechanisms are implemented as independent software services which allows us to integrate them into other systems easily. Beside the integration into OptorSim, this flexibility allows us to integrate the markets into the prototype in the future such as proposed in [CJSF06]. 5.1.1.1 Service Market As outlined in the last deliverable [SNV+05a], a double auction is applied to the service market. In a double auction market [Fri91], a large number of participants trade a common object and can submit bids (buy orders) and asks (sell orders). Trading in 29 CHAPTER 5. INTEGRATION OF MECHANISMS INTO SIMULATOR 30 double auctions is organized by means of order books, each for a set of homogeneous goods. In the CATNETS scenario there will be ndifferent order books, each for one of the ndifferent services. Figure 5.1 depicts the high level architecture of the service market for CATNETS [SNV+05a]. Complex service agents can submit buy orders to the order books; basic service agents can submit sell orders. Each set of homogeneous services (e.g. PDF creator services) is traded in a single order book. Figure 5.1: The service market including several double auction order books. A simplified class diagram of the service market implementation is shown in figure 5.2: For each type of basic service traded in the service market, an instance of the Orderbook class is generated. The order book provides functionality to add orders, remove them, and to start the outcome determination. Whenever an agent wants to submit an order to the market, it generates an instance of the Order class and submits it to the order book. The order book is also responsible for triggering the clearing process. In case, a continuous clearing is used, the order book instantiates the Allocator CDA class; otherwise it uses the call market as implemented in the Allocator CallMarket class. Both allocator classes use the matchmaker Match to find corresponding counterpart orders. After the allocation and the prices are computed, an Allocation object is generated for each transaction. This object points to the parties that are involved in the transaction, i.e. it points to an order from a buyer and an order from a seller. The allocation objects are stored in a vector and can be parsed by the simulator. As the diagram shows, the implementation supports continuous clearing and a call market. In a continuous clearing auction, buyers and sellers simultaneously and asynchronously announce bids and offers. In case a new order enters the market, the auctioneer tries to clear the market immediately. A call market is an auction with periodic CHAPTER 5. INTEGRATION OF MECHANISMS INTO SIMULATOR 31 Figure 5.2: Class diagram of the most fundamental classes of the service market uniform clearing, e.g. the auctioneer clears the market every fives minutes. All orders in a period are collected in an order book and will be cleared periodically [SNV+05a]. The clearing strategy that is applied can be selected by means of a configuration file. Till the end of Y3 we did not succeed in implementing the event driven time model for the continuous clearing auction into the simulator. So it was not possible to speed up simulation runs from real time. Therefore we chose to use the continuous clearing auctions for the simulation runs in Y3. That enabled us to calibrate and evaluate the centralized approach on a lager data set. 5.1.1.2 Resource Market For allocating services in the resource market, we apply a multi-attribute combinatorial exchange (MACE) [SNV+05a, SNVW06]. Figure 5.3 depicts the sequence of the auction in the CATNETS scenario. Agents (buyers and sellers) submit their bids to the auctioneer instance. After that, the bids are transformed into an internal representation form and, subsequently, the winners are computed (allocation). Finally, prices are computed in consideration of the allocation. As a result of the market mechanism, the agents get informed whether or not they are part of the allocation. Figure 5.4 depicts some of the most basic components of the implementation as a UML class diagram: The Market class is the central component of the implementation. On the one hand, it is responsible for initializing all relevant classes. On the other hand, the market class controls the process to submit orders and to compute an outcome. Agents can submit orders to an order book, where an order consists of a price and a CHAPTER 5. INTEGRATION OF MECHANISMS INTO SIMULATOR 32 Figure 5.3: Sequence of an auction for the resource market Bundle, where a bundle is a collection of Good instances. After the bids are submitted by the agents, an Outcome is computed. For this, the market uses a ModelFactory and a PricingFactory. The ModelFactory is responsible for providing a winner determination model in order to compute an allocation. In the CATNETS scenario, this model is implemented in the CatnetsResourceMarket class. The PricingFactory provides a set of price mechanisms that can be used. In CATNETS, the pricing schema as implemented in the KPrice class is applied. After an allocation and corresponding prices are determined, the result is stored in the Outcome object. This object can be queried in order to retrieve the required information such as allocation decisions and prices for each transaction. For implementing the resource market, we make use of the standard linear programming libraries CPLEX and LPSolve. CPLEX is a commercial product and is currently the state of the art optimization engine1. LPSolve is a free linear programming solver that implements the branch-and-bound method for solving integer problems2. CPLEX is currently one of the fastest solving libraries and will be used for the evaluation of the mechanisms. The use of LPSolve (more specifically, its license) allows us to install the resource market implementation on every machine. As such, the development and testing of the mechanisms can be fostered. The behavior of the implementation can be controlled by means of configuration files. Among others, several alternative pricing schemas are implemented, e.g. the approximated Vickrey pricing algorithm [PKE01]. The concrete pricing mechanism can be selected by means of a configuration parameter. Furthermore, the clearing interval3of the 1See http://www.cplex.com/ for details. 2See http://www.geocities.com/lpsolve/ for details. 3The resource market is currently restricted to a periodical clearing. CHAPTER 5. INTEGRATION OF MECHANISMS INTO SIMULATOR 33 Figure 5.4: Class diagram of the most fundamental classes of the resource market market can be controlled by the configuration file. 5.1.2 Integration into OptorSim This section briefly outlines the integration of the markets into OptorSim. For a detailed description of how these concepts are implemented, the reader is referred to deliverable D2.2 [CSSZ06]. In OptorSim, the auctioneers for the service market and resource market are both realized as agents. They get instantiated by the simulator during its initialization and can be contacted by every other agent. Agents communicate with the auctioneers in order to submit their bids and to retrieve status information such as the last market price for a service or the allocation decision. The communication between trading agents and auctioneers is realized by means of messages. Figure 5.5 shows the general interaction between trading agents and an auctioneer. Each time, a complex service agent (CSA) wants to acquire of service, it submits a message to its Peer-to-Peer Manager (P2P). This manager is capable of advertising and routing messages to other agents. In case a manager receives a message from its CSA, it CHAPTER 5. INTEGRATION OF MECHANISMS INTO SIMULATOR 34 forwards the message to the auctioneer (SMAA). Likewise, a basic service agent (BSA) can also submit an offer message to its Peer-to-Peer Manager which also forwards it to the auctioneer. On the basis of the messages, the auctioneer computes an outcome, i.e. allocation decisions and prices. The result of this outcome (successful or unsuccessful bid) is subsequently sent back to the agents. The figure shows the process for the service market exemplarily; for the resource market the process is identical. Figure 5.5: Sequence of an auction for the resource market. The central interfaces between OptorSim and the auctioneers are messages. From a conceptual point of view, different message types are required for different actions of the agents: Request Message: A request message is sent, whenever an agent wants to buy a service. For instance, a complex service agent submits such a message to the auctioneer to bid for a basic service. The message contains information about the transaction object (which service), the agent’s valuation price (maximum price), as well as an ID of the agent. Offer Message: An offer message is sent, whenever an agent wants to sell a service. For instance, a resource service agent submits such a message when it wants to sell its resources. In analogy to the request message, the offer message contains information about the transaction object (which service), the agent’s reservation price (minimum price), as as well as an ID of the agent. Allocation Message: After the auctioneer has computed an outcome, allocation messages are sent back to each participating agent. In case the agent was successful CHAPTER 5. INTEGRATION OF MECHANISMS INTO SIMULATOR 35 in the auction (i.e. it is part of the allocation), the message contains information about the price of the service and its counterpart. For instance, if a basic service agent retrieves a successful allocation message from the resource market auctioneer, the message contains information about the resource service agent who will provide the resources. In case an agent was unsuccessful, the contains a negative price (p=−1). Delete Message: Sometimes agents need to cancel orders which they have submitted to the auctioneer. In this case, they submit a delete message to auctioneer. This message contains all relevant information such as the agent ID and an order ID. Each message type is implemented for the service market and the resource market. The implementation of the messages is described in the deliverable D2.2 in more detail [CSSZ06]. 5.2 Decentralized Mechanisms (Catallaxy) This section briefly outlines the implementation of the decentralized markets and its integration into OptorSim. Section 5.2.1 focuses on the implementation of the decentralized (catallactic) service and resource market. The implementation of the strategy module and its adoption to the markets are described in detail. The integration into OptorSim, message patterns and the introduced message types describes section 5.2.2. 5.2.1 Implementation of the Markets The implementation of the service and resource markets use the catallactic reasoner implementation presented in the deliverable D1.1. Both markets use the same strategy implementation for reasoning about proposals. Therefore, the objective of this section is to describe the implementation of the service and resource market using the catallactic reasoner. Differences between the service and the resource market occur at the initialization of the strategy, their interaction patterns and the integration into the simulator and prototype environment. In the following, the focus lies on the interfaces of the strategy and its initialization. The interaction patterns are dependent on the environment to be integrated. Thus, they are described in their corresponding sections. The interface of the reasoner shows figure 5.6. The implementation offers customized reasoners for every agent type in the CATNETS scenario, which extend the AgentSource reasoner template. The AgentSource class is an implementation of the bilateral negotiation protocol which calls the Avalanche strategy for decision making. Additionally, it provides access to the evolutionary learning algorithm. CHAPTER 5. INTEGRATION OF MECHANISMS INTO SIMULATOR 36 From a conceptual point of view, the agent calls the reasoner with a Msg object which contains all information according to the bidding language presented in the D1.1 deliverable and some additional identification information. The strategy interprets this object (interpretMessage) and returns a Msg object. This process separates the message propagation from the reasoning about the content using the defined negotiation protocol. The underlying infrastructure transports the content to its destination. The same concept is applied in the simulator and prototype environment. «Java Class» AgentSource CLASS_NAME : String strategy : IPricing budget : double AgentSource ( ) getStrategy ( ) interpretMessage ( ) setPrice ( ) setGenotype ( ) decreaseBudget ( ) increaseBudget ( ) interpretCfp ( ) interpretProposal ( ) interpretAccept ( ) interpretReject ( ) postRejectanceMethod ( ) postAcceptanceMethod ( ) checkRestrictions ( ) increasePriceDistribution ( ) decreasePriceDistribution ( ) learn ( ) interpretPlumage ( ) «Java Class» ComplexServiceReasoner ComplexServiceReasoner ( ) postRejectanceMethod ( ) postAcceptanceMethod ( ) execute ( ) «Java Class» CatallacticReasoner createCfp ( ) createResourceCfp ( ) checkRestrictions ( ) postAcceptanceMethod ( ) postRejectanceMethod ( ) «Java Class» BasicServiceReasone r BasicServiceReasoner ( ) BasicServiceReasoner ( ) postRejectanceMethod ( ) postAcceptanceMethod ( ) executeServiceMarket ( ) executeResourceMarket ( ) «Java Class» ResourceReasoner ResourceReasoner ( ) postRejectanceMethod ( ) postAcceptanceMethod ( ) execute ( ) «Java Class» Msg serialVersionUID : long messageType : int documentType : int itemID : String price : double budget : double basicServices : BasicServiceData verdict : int msg_plumage : Plumage hopCounter : int basicService : BasicServiceData market : String smMessage : Object reqMessage : Object «use» «use» «use» «use» «use» Figure 5.6: The interface of the catallactic reasoner. The relevant attributes of the Msg class are in detail: CHAPTER 5. INTEGRATION OF MECHANISMS INTO SIMULATOR 37 MessageType:The type of the negotiation message specifies the communicative act referred to the negotiation protocol. In the bilateral negotiation protocol of the catallactic reasoner the following values are used: cfp (call-for-proposal), accept, reject, proposal. ConversationID:The identifier of the negotiation is an unique number generated for each new request during the creation of new cfp message. The values are random generated UUIDs of the Java built-in UUID generator. DocumentType:This parameter signals the catallactic reasoner the type of price to reason about. A BID refers to the proposal type to be generated by a seller and an ASK relates to a buyer offer. ItemID:This is the identifier of the traded good. In the current implementation, this could be any kind of text. In OptorSim, services usually are identified using their type (cs or bs for complex service or basic service) followed by a number. The bundles on the resource market are identified using a sequence of their single items. For example, ”cpu;mem;hdd” refers to a bundle of the three single bundle items cpu, memory (mem) and hard disk space (hdd). Price:This is the current price of the traded good. On the service market, it is the price for a basic service instance; on the resource market it is the price for a resource bundle. In the current implementation, there is a predefined price for every resource bundle combination. The agent has a preference for trading certain resource bundles. Market:The market parameter is used to assign the message to a market. In the CATNETS scenario, the values are: SERVICEMARKET, RESOURCEMARKET Verdict:This is the verdict on bid set by the strategy. It relates to the result of the catallactic reasoner. Valid values are: accept, reject, proposal Plumage:The plumage parameter represents a container for learning information. This container includes the fitness information and the genotype values of other agents which traded the same good. The market agents use the described message object to decide the next operation. This operation is dependent on the message type of the market agent and its role in the market. Its general bidding behavior forming the two market is described in section 4.2. The implementation of the agents follows this description. The next section presents the initialization of strategy for the two markets in the CATNETS scenario. initialization of the strategy for the service and resource market: The initialization of the reasoner splits into two areas: The first area is the initialization of the items and CHAPTER 6. RELATIONS TO OTHER WPS 44 6.3 WP4 The goal of WP4 is to evaluate the performance of the Catallactic approach by means of a simulator (see deliverable year 2 of WP2) and a prototype (see deliverable year 2 of WP3). The relations to WP4 are as follows: •The identification and formalization of relevant metrics to compare centralized and decentralized market mechanisms. •Collaboration with the development of the performance measuring framework, due to the fact that some of the measured metrics are taken at the economic agent level. Reporting of measured data to the performance measuring framework. Chapter 7 Summary In this chapter the achievements from workpackage 1 during Y2 and Y3 of the project are summarized. Section 7.1 focuses on the work that has been performed in Y2 and Y3. A brief review is given on how this relates to the first project year. In Section 7.2 the tasks performed in Y3 are specified. Finally section 7.3 puts the CATNETS results into a greater perspective. 7.1 Review As described in the introduction and in the project summary, the main contribution of the CATNETS project is the comparison of centralized and decentralized economic allocation mechanisms for resources in Grids and application layer networks (ALNs). In order to achieve this, the project has been divided into five workpackages. The content of the individual workpackage as well as the division and integration of those has been elaborated on in Chapter 1 and Chapter 6. In this report, the line of work carried out in the second project year (month 25 to month 48) is described. Thereby, Chapter 3 focuses on the formal description of the centralized and decentralized mechanisms. The centralized mechanisms, which also have been content to year 1 report, are briefly discussed and an in depth presentation of the decentralized mechanisms as well as the learning algorithms and negotiation strategies is given. The notion of two different markets – a resource and a service market – is introduced. Both markets are interconnected via a intermediaries. After this, Chapter 4 clarifies when and what a participant in resource and service markets bids. The definitions provided here are substantial for the design of both (i) the implementation of the mechanisms in the simulator as well as (ii) the integration of the decentralized mechanisms into the middleware. In Chapter 5 the integration of the centralized and decentralized mechanisms into the 45 CHAPTER 7. SUMMARY 46 OptorSim simulator framework is described. Besides the preparatory work that is content to the chapters before, this has been the most demanding and extensive work that has been carried out in workpackage 1 in year 2. The challenge here is to provide a flexible, adaptable and dynamic simulation framework that enables both, simulations based on centralized and decentralized market setups in one scenario in order to keep the results comparable. Additionally to the issues concerning the implementation itself, simulation results from both, the centralized and the decentralized case are compared to each other. 7.2 Content to Y3 After the integration of the centralized and the decentralized economic mechanisms into the simulator and the integration of the centralized mechanism into the middleware was finished and refined the following tasks were the main issues for workpackage 1: •2.3 Simulation of application layer networks and refinement: Here, the efforts in workpackage 1 was focused on the calibration, validation and verification of the simulation model. Additional issues were the assistance of workpackage 2 leaders in carrying our simulations, obtaining and evaluating large-scale data from simulation runs as well as to interpret the results derived from the applied metrics. •3.3 Performance measuring components for experiments: Concerning this issue, most work is carried out in workpackage 3. However, the economic expertise in designing and monitoring the performance evaluation both, from a technical and an economic perspective has been our mission in year 3. •3.4 Distributed application to execute on economic-enhanced Grid/P2P platform and middleware integration: In this task, the integration of middleware concepts for novel approaches in Grid and P2P architectures was evaluated. Besides generating substantial results, the target of workpackage 1 was her to assist workpackage 3 leaders in provisioning of a strong footprint of the work performed in CATNETS in the Grid/SOA/P2P/Pervasive Computing communities. •4.4 Performance analysis, comparison, evaluation: As to all other participants, it was one of the core issues to analyze, document and compare the evaluation of the proposed mechanisms. Workpackage 1 contributed to this effort by assisting workpackage 4 protagonists in order to show the efficiency and effectiveness of the proposed mechanisms in appropriate scenarios and find channels to distribute these results into all relevant communities. CHAPTER 7. SUMMARY 47 7.3 Outlook The core contribution of the CATNETS project is the quantitative comparison between common centralized economic allocation mechanisms and decentralized negotiation formats based on von Hayek’s Catallaxy. Therefore, several metrics have been defined in order to identify the quality of the economic allocations. The results show, that the applicability of allocation mechanisms highly depends on the parameterization of the individual setup. Core issues along which the identification of the appropriate mechanism has to be aligned at are: • the size of the allocation problem, • the communication intensity, • the distribution of the prices offered by the participants and • the dynamics of the market. All these parameters again depend upon the industry branch in which the individual application, for which the mechanism should be deployed, is located. The approaches investigated within the CATNETS project may be subsumed in the field of Grid Economics. In this field, currently strong efforts are bundled in order to identify methodologies that are applicable for dynamically allocating computational resources to applications. The vision of this field is to enable a seamless integration of distributed hardware for the computation of heterogeneous front-end applications. The idea is to allow for dynamic allocation of resources in order to determine the prices of computational resources along the time. In order to lay the fundaments for such an architecture, substantial efforts have to be carried out in the Grid middleware domain. Applying the results from CATNETS anticipates a fully functional Grid middleware, which is capable of ex-ante determining the time specific jobs are running. This implies a component, which judges the runtime of jobs stemming from heterogeneous applications. Having such a component in place will allow the application of market based allocation schemes such as they have been proposed in this work. The key ideas of our approaches have been presented in different communities. A large number of experts from the e-Infrastructure community, the Grid community as well as the SOA and the distributed systems communities see great potential in these approaches. Several in depth cooperations have been started here. Bibliography [AG04] Nadia Ben Azzouna and Fabrice Guillemin. Charcteristic of ip traffic in commercial wide area networks. In Proceedings of the International Conference on Computing, Communcations and Control Technologies (CCCT’2004), Austin, Texas (TX), August 2004. [AH00] E. Adar and B.A Huberman. Free riding on gnutella. First Monday, 5(10), 2000. [BCC+07] Georg Buss, Michele Catalano, Pablo Chacin, Isaac Chao, Torsten Eymann, Felix Freitag, Sebastian Hudert, Liviu Joita, Leandro Navarro, Nils Parasie, Omer F. Rana, Bj¨orn Schnizler, Werner Streitberger, and Daniel Veit. D4.3: Performance evaluation. Catnets deliverable, University of Mannheim,Universit´a delle Marche Ancona, Universitat Politecnica de Catalunya, University of Bayreuth, University of Karlsruhe, University of Cardiff, 2007. [Bre02] T. Brenner. A behavioural learning approach to the dynamics of prices. Computational Economics, pages 67–94, 2002. [Car04] Nicholas G. Carr. Does IT Matter? Information Technology and the Corrosion of Competitive Advantage. Harvard Business School Press, May 2004. [CGS+05] Michele Catalano, Gianfranco Giulioni, Werner Streitberger, Michael Reinicke, and Torsten Eymann. 4.1: Evaluation and metrics framework. Catnets deliverable, Universit´a delle Marche Ancona, University of Bayreuth, 2005. [CJSF06] P. Chacin, L. Joita, B. Schnizler, and F. Freitag. Flexible architecture for supporting auctions in grids. In Proceedings of the 2nd International Workshop On Smart Grid Technologies 2006 (SGT2006) Workshop, 2006. [CSSZ06] Gaetano Calabrese, Bj¨orn Schnizler, Werner Streitberger, and Floriano Zini. D2.2: Annual report of wp2. Catnets deliverable, ITC-irst Trento, University of Karlsruhe, University of Bayreuth, 2006. 48 BIBLIOGRAPHY 49 [ESH07] Torsten Eymann, Werner Streitberger, and Sebastian Hudert. 5.6: Periodic progress report. Catnets deliverable, University of Bayreuth, 2007. [ESMP03] T. Eymann, S. Sackmann, G. M¨uller, and I. Pippow. Hayek’s catallaxy: A forward-looking concept for information systems. In Proceedings of the American Conference on Information Systems (AMCIS), Tampa, Florida, 2003. [ESP98] Torsten Eymann, Detlef Schoder, and Boris Padovan. Avalanche - an agent based value chain coordination experiment. In Workshop on Artificial Societies and Computational Markets (ASCMA’98), pages 48–53, Minneapolis, 1998. [Eym01] Torsten Eymann. Decentralized economic coordination in multi-agent systems. In Hans-Ulrich Buhl, F. Huther, and A. Reitwiesner, editors, Information Age Economy. Proceedings WI-2001., pages 575–588, Heidelberg, 2001. Physica Verlag. [Fri91] D. Friedman. The double auction market institution: A survey. In D. Friedman and J. Rust, editors, The Double Auction Market - Institutions, Theories, and Evidence, pages 3–26. Cambridge MA, Perseus Publishing, 1991. [HBKC89] F.A.v. Hayek, W.W. Bartley, P.G. Klein, and B. Caldwell. The collected works of f.a. hayek. University of Chicago Press, 1989. [KC03] Jeffrey O. Kephart and David M. Chess. The vision of autonomic computing. Computer, 36(1):41–50, January 2003. [KR95] J.H. Kagel and A.E. Roth. The handbook of experimental economics. Princeton University Press, 1995. [Mat99] Humberto R. Maturana. The organization of the living: a theory of the living organization. Int. J. Hum.-Comput. Stud., 51(2):149–168, 1999. [PKE01] David C. Parkes, Jayant Kalagnanam, and Marta Eso. Achieving budgetbalance with vickrey-based payment schemes in exchanges. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, 2001. [Pru81] D.G. Pruitt. Negotiation behavior. Organizational and occupational psychology. New York: Academic Press, 1981. [PT02] W. H. Press and S. A. Teukolsky. Numerical Recipes in C++ - The Art of Scientific Computing. Cambridge, MA, Cambridge University Press, 2002. [RFH+01] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Schenker. A scalable content-addressable network. Technical report, Berkeley Press, 2001. BIBLIOGRAPHY 50 [Ros94] G. Rosenschein, J. S.; Zlotkin. Rules of encounter - designing conventions for automated negotiation among computers. MIT Press, Cambridge, 1994. [Smi62] V.L. Smith. An experimental study of competitive market behavior. Journal of Political Economy, 70:111–137, 1962. [SNV+05a] Bj¨orn Schnizler, Dirk Neumann, Daniel Veit, Mauro Napoletano, Michele Catalano, Mauro Gallegati, Michael Reinicke, Werner Streitberger, and Torsten Eymann. f: Environmental analysis for application layer networks. Catnets deliverable, University of Karlsruhe, Universit´a delle Marche Ancona, University of Bayreuth, 2005. [SNV+05b] Bj¨orn Schnizler, Dirk Neumann, Daniel Veit, Michael Reinicke, Werner Streitberger, Torsten Eymann, Felix Freitag, Isaac Chao, and Pablo Chacin. Deliverable 1.1; wp 1: Theoretical and computational basis. Technical report, CATNETS, 2005. [SNVW06] Bj¨orn Schnizler, Dirk Neumann, Daniel Veit, and Christof Weinhardt. Trading Grid Services – A Multi-attribute Combinatorial Approach. European Journal of Operational Research, forthcoming, 2006. [Tes97] L. Tesfatsion. How economists can get alife. In The Economy as a Evolving Complex System II, pages 533–564. Arthur, W.B. and Durlauf, S. and Lane, D.A. (Hrsg.), 1997. [Var94] Hal R. Varian. Mikrokonomie. Oldenbourg, 1994. [Wei99] Gerhard Weiss, editor. Multiagent systems: a modern approach to distributed artificial intelligence. MIT Press, Cambridge, MA, USA, 1999. [Wie98] N. Wiener. The history and prehistory of cybernetics. Kybernetes, 27:29–37, 1998. ISSN In this document the developments in defining the computational and theoretical framework for economical resource allocation are described. Accordingly the formal specification of the market mechanisms, bidding strategies of the involved agents and the integration of the market mechanisms into the simulator were refined. 1864-9300