Optimal scalability of a distributed algorithm 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.