Distributed Commerce Transactions with Timing Deadlines and Direct Trust

Abstract

In a multi-party transaction such as fulfilling an information request from multiple sources (also called a distributed commerce agents face risks from dealing with untrusted agents. These risks are compounded in the face of deadlines, e.g., an agent may fail to deliver purchased goods by the time the goods are needed. We present a distributed algorithm that mitigates these risks, showing that it is sound (produces only safe multi-agent action sequences) and complete (finds a safe sequence whenever one We also show how the algorithm may be extended so that agents may interact directly with other participants rather than through a trusted intermediary. Introduction The explosion of networked information sources leads to the sense that the answer to any question is out there, if only one has access to the right combination of sources. Search engines and information brokers help navigate the space, yet adding information services and sources which require payment exposes a number of hazards. A transaction with a customer, brokand source(s) involves the following risks: 1. A customer spends money without receiving the promised document in time. 2. A broker or source sends a document to a customer without receiving payment. 3. A customer with a conjunctive request pays for one document without being able to obtain all of the others in time. (This risk is known as "buying half a conjunction.") 4. A broker buys a document but has its customer back out, leaving no one to re-purchase the document. In (Authors 1996a; 1996b; we define a distributed commerce transaction where agents playing the roles of customer, broker, or source interact with each other through trusted intermediaries. The goal is to move documents from the sources to the customer. This problem is complicated by two factors. First, agents have a limited set of actions (sending a document or money, requesting a document or money, or Figure 1: A simple example returning a document or money, notifying pending st