Estudiamos la clase de redes que pueden ser creadas en tiempo paralelo polilogarítmico por constructores de redes: grupos de agentes anónimos que interactúan aleatoriamente bajo un programador aleatorio uniforme con la capacidad de formar conexiones entre ellos. Partiendo de una red vacía, el objetivo es construir una red estable que pertenezca a una familia dada. Demostramos que la clase de árboles donde cada nodo tiene al menos k>=2 hijos puede ser construida en O(logn) tiempo paralelo con alta probabilidad. Mostramos que construir redes que son k-regulares toma Ohm(n) tiempo, pero una relajación mínima a redes (l,k)-regulares, donde l=k-1, puede ser construida en tiempo paralelo polilogarítmico para cualquier k fijo, donde k>2. Además, demostramos que cuando se relaja la suposición de estado finito y se permite que k crezca con n, entonces k=loglogn actúa como un umbral por encima del cual la construcción de redes es, nuevamente, tiempo polinómico. Usamos esto para proporcionar una caracterización parcial de la clase de constructores de redes de tiempo polilogarítmico.