Deje que la clase BPNC (la combinación de y ) sean algoritmos paralelos de profundidad logarítmica con probabilidad de error limitada y acceso a una fuente aleatoria (no estoy seguro si este tiene un nombre diferente). Defina la clase DBPNC de manera similar, excepto que todos los procesos tienen acceso aleatorio a una secuencia aleatoria de bits fijos al inicio del algoritmo.N C
En otras palabras, cada proceso en BPNC tiene acceso a una fuente aleatoria distinta, mientras que los algoritmos DBPNC tienen un generador de modo contador totalmente aleatorio compartido.
¿Sabemos si BPNC = DBPNC?
Respuestas:
Son lo mismo: BPNC = DBPNC.
Digamos que una máquina BPNC recibe como entrada un programa DBPNC para simular. Ejecute el programa en el paso de bloqueo. Primero suponga que los índices entre los diferentes pasos son distintos, por lo que no necesitamos recordar bits aleatorios antiguos. En cada paso, cada procesador solicita un bit aleatorio en un índice específico en la secuencia compartida. Calcule y distribuya los bits aleatorios de la siguiente manera:
Para permitir que los procesadores soliciten índices antiguos, haga que cada procesador recuerde los (resultados) de todas las épocas de clasificación anteriores. Para verificar si los índices recién solicitados ocurrieron en una época anterior dada, haga
fuente