However, as the transaction becomes more complex, involving multiple sources and information brokers, it is not clear that there will be a single intermediary that all will trust. Instead, we assume only that pairs of agents who wish to make an exchange can find an intermediary which the two of them can trust. Consequently, a single multi-party exchange will be broken into several two-party exchanges, each using a (potentially) different trusted intermediary. The ordering in which the pair-wise exchanges are executed is critical, since some situations place control of the successful completion of the transaction in the hands of an untrusted agent. For example, a customer who wishes to obtain two documents and finds only their conjunction useful may be disappointed to spend half of his money to obtain one document, with the second being unavailable. Similarly, a broker may purchase a document in order to re-sell it to a customer, only to find the customer is no longer willing to buy it. Indeed some transactions simply cannot be broken down to a sequence of pairwise transactions that protects all of the parties involved.
In [kgm96], we introduce the notion of a distributed transaction, which describes the agents involved in a transaction, their connectivity, resources, and available actions. The goal of performing a riskless distributed transaction is to locate a sequence of actions that makes use of only pair-wise exchanges through locally trusted intermediaries. The action sequence should achieve some desired outcome while never causing an agent to run the risk of ending in an undesirable state, even if other agents deviate from their expected actions.
A tech report in preparation [kgm96b] gives a distributed algorithm for finding riskless action sequences. The algorithm is proven sound and complete, so that it will never generate an unsafe sequence, and if a sequence exists, the algorithm will find it. Extensions for cases where one agent does directly trust another and the presence of hard, real-time deadlines are also shown sound and complete. Future work will develop these notions in a decision theoretic framework, permitting agents to take risky actions if they have a positive expected utility. Soft deadlines (decreasing utility over time) will also be modeled.
[kgm96] Ketchpel, Steven P. and Hector Garcia-Molina. "Making Trust Explicit in Distributed Commerce Transactions". In International Conference on Distributed Computing Systems (DCS '96). Available at: http://db.stanford.edu/~ketchpel/papers/DCS96/distributed-transactions.ps
[kgm96b] Ketchpel, Steven P. and Hector Garcia-Molina. "A Sound and Complete Distributed Algorithm for Distributed Commerce Transactions." Stanford Digital Library Working Paper SIDL-1996-0040. Preliminary draft available at: http://www-diglib.stanford.edu/cgi-bin/WP/get/SIDL-WP-1996-0040
For more information, contact ketchpel@hotspur.stanford.edu