Mechanism Design for Grid Computing

We develop a system for grid computing where the price of computing tasks is determined by an audited market-exchange. We show a method to provide a variable certificate, called \witness," of program execution with the following property: If two different agents running the same program on the same input produce the same witness, that proves with certainty very close to 1 that both agents have executed the program correctly. Using these witnesses, a trusted intermediary audits grid agents by dispatching identical work units to different agents and comparing their results. The results of past audits create a reputation history for agents, which is used to offer different prices to consumers based on the expected reliability corresponding to a reputation history. We allow reputations to be traded, instead of being tied to individual agents, and we show that in such a reputation market only high-type agents would have incentive to purchase a high reputation, and only low-type agents would use low reputations