Structures.

Providing market structure only partially solves resource-allocation problems; an agent must be able to interact with the market and plan to complete its goals. Towards this end, we studied many different auction schemes in which agents bid for computational resources [BKR98b,BKR99c,BMcI+99,BMcI+00,BKR+01b,BKR01a,Bre01a]. We found a tradeoff in the information regarding preferences agents disclosed and efficiency of the market and in the complexity required to calculate prices [BKR01a,Bre01a].

Most of the market mechanisms we studied were demand driven. An agent purchased resources immediately prior to use. To alleviate risk, however, we instrumented call options in our market where agents could purchase a contract to guarantee computation at a fixed price in the future. We extended the Cox, Ross, Rubinstein option-pricing model to allow agents to integrate demand and reservation-based computing according to their preference towards risk [BKR00,Bre01a].

Each of the planning algorithms we implemented relied on estimates of an agent's planned consumption. In real-life applications, resource use is difficult to forecast, so we tested our algorithms using flawed estimates to find that our algorithms adapted an agent's plans as the estimation errors became more apparent [Bre01a,BMcI+03]. Finally, we implemented our resource-allocation and planning algorithms as part of a Linux real-time kernel scheduling process to regulate mobile processes [CG00].

There are 17 papers in this category [BKR98b,BKR98c,BMcI+00,BKR+01b,BMcI+99,BKR01a,BMcI+03,BKR99b,BKR99c,BKR98a,BKR97,BKR99a,BKR00,Bre01a,Bre01b,CG00].