How to convert a centralized algorithm to a distributed algorithm?

Question

Is there any algorithm or procedure to convert a centralized algorithm to a distributed algorithm? Is there any theoretical result or relevant complexity analysis?

Answer 1

Sure. If you have a distributed system with N machines, you can always run the centralized algorithm on machine 1 and let machines 2..N sit idle.

If you're asking whether all sequential algorithms can be parallelized, that's an open question, but it's believed that the answer is no: see the NC complexity class. As Wikipedia states,

there are probably some tractable problems that are "inherently sequential" and cannot significantly be sped up by using parallelism.

P-complete problems are good candidates for problems that are likely not amenable to speedup by parallelism.

If you're asking whether all algorithms can be made reliable in a distributed system, that is a subtle question that depends on what kinds of failures you are considering. You might look into consensus protocols, state machine replication, and the CAP theorem.