What's the optimal scalability of some algorithm when I implement it in a distributed manner?

Intuitively, it seems to me that any algorithm can scale at most linearly with number of computing nodes. I.e, if algorithm A takes T units of time with 1 computing node on input I, it can't run faster than T/n units of time with n computing nodes on the same input I.

Is my intuition correct or are there some weird counter-examples to it?


Yes, your intuition is correct, for all the reasonable models of computation that I'm familiar with. If it weren't, then we could take a single machine and have it simulate a cluster of n nodes, increasing the cost by only a factor of n. So, if you had an algorithm that ran on a cluster of n nodes faster than T/n, you'd get an algorithm that runs on a single node faster than T.

Note that the single node might need to have n times as much memory as each node in the cluster.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.