Gesellschaft für Informatik e.V.

Lecture Notes in Informatics

10th International Conferenceon Innovative Internet Community Systems (I2CS) - Jubilee Edition 2010 - P-165, 507-518 (2010).

Gesellschaft für Informatik, Bonn

Copyright © Gesellschaft für Informatik, Bonn


Impossibility results on fair exchange

Benoît Garbinato and Ian Rickebusch


The contribution of this paper is threefold. First, we propose a novel specification of the fair exchange problem that clearly separates safety and liveness. This specification assumes a synchronous model where processes communicate by message passing and might behave maliciously. In this model, we prove a first impossibility related to the notion of trust, stating that no solution to fair exchange exists in the absence of an identified process that every process can trust a priori. Finally, we derive an enriched model where processes are divided into trusted and untrusted processes, and we show that an additional assumption is still necessary to solve fair exchange. Intuitively, this result expresses a condition on the connectivity of correct but untrusted processes with respect to trusted processes. We also revisit existing fair exchange solutions described in the literature, in the light of our enriched model, and show that our second impossibility result applies to them.

Full Text: PDF

Gesellschaft für Informatik, Bonn
ISBN 978-3-88579-259-8

Last changed 04.10.2013 18:31:32