Distributed Computing With the Cloud

We investigate the effect of omnipresent cloud storage on distributed computing. We specify a network model with links of prescribed bandwidth that connect standard processing nodes, and, in addition, passive storage nodes. Each passive node represents a cloud storage system, such as Dropbox, Google Drive etc. We study a few tasks in this model, assuming a single cloud node connected to all other nodes, which are connected to each other arbitrarily. We give implementations for basic tasks of collaboratively writing to and reading from the cloud, and for more advanced applications such as matrix multiplication and federated learning. Our results show that utilizing node-cloud links as well as node-node links can considerably speed up computations, compared to the case where processors communicate either only through the cloud or only through the network links. We provide results for general directed graphs, and for graphs with ``fat'' links between processing nodes. For the general case, we provide optimal algorithms for uploading and downloading files using flow techniques. We use these primitives to derive algorithms for \emph{combining}, where every processor node has an input value and the task is to compute a combined value under some given associative operator. In the case of fat links, we assume that links between processors are bidirectional and have high bandwidth, and we give near-optimal algorithms for any commutative combining operator (such as vector addition). For the task of matrix multiplication (or other non-commutative combining operators), where the inputs are ordered, we present sharp results in the simple ``wheel'' network, where procesing nodes are arranged in a ring, and are all connected to a single cloud node.