In a federation of heterogeneous nodes that organize themselves, the lack of a trusted third party does not allow establishing a priori trust relationships among strangers. Automated trust negotiation (TN) is a promising approach to establish sufficient trust among parties, allowing them to access sensitive data and services in open environments. Although the literature on TN is growing, two key issues have still to be addressed. The first one concerns a typical feature of real-life negotiations: we are usually willing to trade the disclosure of personal attributes in exchange for additional services and only in a particular order (according to our preferences). The second one concerns dependability. By their nature TN systems are used in unreliable contexts where it is important not only to protect negotiations against malicious attack (self-protection), but also against accidental failures (self-healing). In this paper we address these issues proposing a novel dependable negotiation framework where services, needed credentials, and behavioral constraints on the disclosure of privileges are bundled together. (C) 2008 Elsevier B.V. All rights reserved.