We are entering an era in which federated information systems are widely used to share information and computation. Federated systems support new services and capabilities by integrating computer systems across independent administrative domains. Each domain has policies for security, but does not fully trust other domains to enforce them. This dissertation explores, in two parts, the challenge of designing and building federated information systems that are secure and reliable while supporting mutually distrusting participants. First, this dissertation presents Fabric, a new system and language for building secure federated information systems. Fabric allows heterogeneous network nodes to securely share information and computation despite mutual distrust. It uses optimistic, nested transactions to ensure global consistency, and has a peerto-peer dissemination layer for better availability and load balancing. Fabric's high-level programming language provides a rich, Java-like object model, and keeps distribution and persistence largely transparent to programmers. It supports data shipping and function shipping: both information and computation can move between nodes to meet security requirements or to improve performance. Confidentiality and integrity policies on objects are enforced through a combination of compile-time and run-time mechanisms. Results from building Fabric applications suggest that Fabric has a clean and concise programming model, offers good performance, and enforces security. Next, this dissertation examines the security implications of providing referential integrity in a federated system. Referential integrity ensures that named resources can be accessed when needed. This is an important property for re- liability and security. However, the attempt to provide referential integrity can itself lead to security vulnerabilities that are currently not well understood. This dissertation identifies three such referential security vulnerabilities, and formalizes security conditions corresponding to their absence. A language model captures key aspects of programming distributed systems with named, persistent resources in the presence of an adversary. A new type system is proved to enforce the conditions for referential security.