Paper accepted by IEEE Transactions on Parallel and Distributed Systems