An improved scalable object storage system allows multiple clusters to work together. In one embodiment, a trust and federation relationship is established between a first cluster and a second cluster. This is done by designating a first cluster as a trust root. The trust root receives contact from another cluster, and the two clusters exchange cryptographic credentials. The two clusters mutually authenticate each other based upon the credentials, and optionally relative to a third information service, and establish a service connection. Services from the remote cluster are registered as being available to the cluster designated as the trust root. Multi-cluster gateways can also be designated as the trust root, and joined clusters can be mutually untrusting. Two one-way trust and federation relationships can be set up to form a trusted bidirectional channel.