Google does give up on determinism when they can. Search is a great example, ask 1,000 machines to give their top 10 results and if 5 don't respond in time your still 99.5% sure that the top result is still the 'best' one. And even if you did lose your best result changes are the rest of the list is still going to be good enough.

Sure, but that's actually a positive and allows special case optimizations of the existing algorithms. My point is this certainly doesn't mean that everything we know is wrong, in fact we have been dealing with this class of problem "in the wild" for last 5-10 years with cloud/cluster computing and GPGPU. Also I feel this "many core is just around the corner" is a lot of hype and little actual results considering that Intel was announcing 70 core CPU by 2011 back in 2007 and we barely hit the 16 cores with AMD. There are some exotic CPUs and GPUs but nothing mainstream, desktops are still at 4-8 core ceiling, mobile is the same. Hopefully SOC GPUs with OpenCL support become mainstream, that will allow interesting things in the mobile space with, but beyond that I don't see this trend hitting the industry any time soon, eg. in 5+ years.