A Sound and Complete Algorithm for Distributed Commerce Transactions

Abstract

In a multi-party transaction such as fulfilling an information request from multiple sources (also called a distributed commerce transaction), 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 algortihm that mitigates these risks, by generating a safe sequence of actions (when possible) that completes a commerce transaction with no risk. We show that the algorithm is sound (produces only safe multi-agent action sequences) and complete (finds a safe sequence whenever one exists). We also show how the algorithm may be extended so that agents may interact directly with other participants rather than through a trusted intermediary.