A cloud does not have infinite computational and storage resources in its infrastructure. If it saturates, it will not be able to satisfy new requests for service allocations sent by its customers. Clouds should interrelate through networking protocols in order to provide scalability, efficiency and flexibility by using the services and the computational and storage resources of the infrastructures of other clouds. In this paper we describe an architecture and protocol that allows exchanging information, data, services, computing and storage resources between all interconnected clouds. It is highly scalable and permits to add new clouds easily, while tries to balance the load of the nodes involved in the intercloud communication. Our protocol design includes node discovery, authentication and fault tolerance. We show the protocol operation and provide the performance results in a con- trolled test bench. A comparison of our architecture and protocol with other published intercloud architecture proposals shows the benefits of implementing this new architecture in the real world.