¿Cómo convertir un algoritmo centralizado a un algoritmo distribuido?

Question

¿Hay algún algoritmo o procedimiento para convertir un algoritmo centralizado a un algoritmo distribuido?¿Hay algún resultado teórico o análisis de complejidad relevante?

Answer 1

seguro. Si tiene un sistema distribuido con máquinas N, siempre puede ejecutar el algoritmo centralizado en la máquina 1 y deje que las máquinas 2..n se sientan inactivos.

Si está preguntando si todos los algoritmos secuenciales pueden ser paralelizados, esa es una pregunta abierta, pero se cree que la respuesta es no: vea la Clase de complejidad de NC . Como estados Wikipedia,

Probablemente hay algunos problemas tratables que son "inherentemente secuenciales" y no pueden acelerarse significativamente utilizando el paralelismo.

Los problemas completos son buenos candidatos para problemas que probablemente no son susceptibles de acelerar por paralelismo.

Si está preguntando si todos los algoritmos se pueden hacer confiables en un sistema distribuido, es decir, una pregunta sutil que depende de qué tipo de fallas está considerando. Puede mirar en protocolos de consenso , Replicación de la máquina de estado , y la TEOREMA CAP .