Abstract: Network virtualization is a key enabling technology for “Infrastructure as a Service” provisioning, increasing the flexibility and cost savings offered to customers. By extending the concept of server virtualization to the network infrastructure, the allocation of different, independent virtual networks over a single physical network is carried out on demand. A fundamental challenge in network virtualization systems is to choose which physical nodes and links to use for hosting virtual networks in the physical infrastructure, known as the “virtual network allocation” problem. All virtual network allocation proposals on elastic optical networks assume a centralized operation, deploying a single node with access to the network state global information and assigning resources accordingly. However, such configuration might exhibit the inherent problems of centralized systems: survivability and scalability. In this paper, we present a distributed protocol for resource discovery, mapping, and allocation of network virtualization systems. The distributed protocol is generic enough as to be used with different substrate networks. However, in this paper, it has been adapted to work over an elastic optical network infrastructure, where further considerations regarding the spectrum continuity and contiguity constraints must also be taken into account. The distributed protocol is based on the concept of alliances: upon the arrival of a virtual network request, agents located in the physical network nodes compete to form the first alliance able to host the virtual network. Because the first alliances to be formed are also the ones composed by nearby nodes, a good network resource usage is achieved. The feasibility of the distributed protocol was studied by evaluating its ability to successfully establish virtual networks within acceptable time and with low bandwidth consumption from the coordination messages.