The Taub Faculty of Computer Science Events and Talks

We study a hybrid distributed model, which combines message-passing and shared-memory communication layers, and investigate the minimal number of failures that can partition such systems. We prove that this number precisely captures the resilience that can be achieved by algorithms that implement a variety of shared objects and solve common tasks, like approximate agreement. In the cluster-based model, processes are partitioned into disjoint clusters. We solve the approximate agreement problem in this model, and its generalization to higher dimensions, multidimensional approximate agreement. Then, we turn our attention to Stochastic Gradient Decent (SGD) algorithms. SGD is widely used for approximating the minimum of a cost function Q, a core part of optimization and learning algorithms. For a strongly convex Q, our algorithm can withstand partitions of the system, and provides convergence rate that is the maximal distributed acceleration over the optimal convergence rate of sequential SGD. For arbitrary smooth functions, the algorithm obtains the same convergence rate as sequential SGD, up to a logarithmic factor. This is achieved by using, at each iteration, a multidimensional approximate agreement algorithm. We complement this result with a lower bound showing that under system partition, some non-convex functions cannot be optimized using a distributed algorithm.