This version is almost identical to the paper published in Theory of Computing Systems (and includes the IPDPS paper).