La técnica de ensayos múltiples de Schneider et al. se emplea para algoritmos distribuidos y permite romper la simetría de manera eficiente. La ruptura de la simetría es necesaria, por ejemplo, en problemas de asignación de recursos, donde muchas entidades quieren acceder al mismo recurso simultáneamente. Muchos algoritmos de paso de mensajes suelen emplear un intento de romper la simetría por cada intercambio de mensajes. La técnica de ensayos múltiples trasciende este enfoque al emplear más intentos con cada intercambio de mensajes. [1]
Por ejemplo, en un algoritmo simple para calcular una coloración de vértice O(Δ) , donde Δ denota el grado máximo en el gráfico, cada nodo no coloreado elige aleatoriamente un color disponible y lo conserva si ningún vecino (al mismo tiempo) elige el mismo color. Para la técnica de ensayos múltiples, un nodo aumenta gradualmente el número de colores elegidos en cada ronda de comunicación. La técnica puede producir más que una reducción exponencial en las rondas de comunicación requeridas. Sin embargo, si el grado máximo Δ es pequeño, existen técnicas más eficientes, por ejemplo, la técnica (extendida) de lanzamiento de moneda de Richard Cole y Uzi Vishkin . [2]