More Effective Distributed ML via a Stale Synchronous Parallel Parameter Server
We propose a parameter server system for distributed ML, which follows a Stale Synchronous Parallel (SSP) model of computation that maximizes the time computational workers spend doing useful work on ML algorithms, while still providing correctness guarantees. The parameter server provides an easy-to-use shared interface for read/write access to an ML model's values (parameters and variables), and the SSP model allows distributed workers to read older, stale versions of these values from a local cache, instead of waiting to get them from a central storage. This significantly increases the proportion of time workers spend computing, as opposed to waiting. Furthermore, the SSP model ensures ML algorithm correctness by limiting the maximum age of the stale values. We provide a proof of correctness under SSP, as well as empirical results demonstrating that the SSP model achieves faster algorithm convergence on several different ML problems, compared to fully-synchronous and asynchronous schemes.
The paper presents an approach to building a parameter 
      server for distribute ML systems that presents a view to each client where 
      parameters have a bounded degree of staleness. Using a combination of 
      caches, the client interface guarantees that all updates to the parameter 
      array occurring after a fixed deadline (the current clock/iteration/tick 
      minus a fixed delay) are visible along with more recent updates if 
      possible. Thus the interface presents a view of parameters that integrates 
      most updates along with best-effort service for more recent updates. It is 
      shown that this simple semantic preserves the theoretical guarantees of 
      cyclic delay methods while being significantly faster in practice. 
      Empirical analysis on several problems with multiple cluster 
      configurations show that the advantage is due to a combination of 
      increased efficiency (over BSP) and optimization progress per update (over 
      Asynchronous). This paper presents a simple set of semantics that 
      improve on "parameter server" schemes currently showing up in large scale 
      machine learning applications. Along with straight-forwardly carrying over 
      simple theoretical guarantees, the method is apparently significantly 
      faster for reasonably-sized tests than the obvious competitors and on 
      those points alone I think this is pretty positive. There are a 
      lot of well-known problems in loaded clusters (stragglers, etc.) and as 
      far as I can tell this approach should deal with them well. A saving grace 
      may be that the caching mechanism reduces overhead dramatically for the 
      slowest nodes thus giving a degree of "load balancing" that is annoying 
      hard to get in other ways. Is it possible to show that this is actually 
      happens to a degree sufficient to enable the "catch up" phenomenon claimed 
      in the paper? Some discussion of the read semantics is given with 
      details on the cache policy (which just falls through when the local cache 
      is stale). Due to the read-my-writes policy, is it correct that all local 
      writes are written through to all caches/server? A sentence of 
      clarification on the writing semantics might help for reproduction of the 
      work. As far as systems papers go the authors make a good case for 
      the approach. Pros: Fairly simple semantics. Preserves 
      basic theoretical guarantees for typical methods (e.g., SGD). 
      Experimental analysis shows actual speedups on multiple distributed 
      problems and the speedup comes from the sources expected. Cons: 
      A comparison to cyclic delay would be nice. Potentially complex to 
      re-implement in comparison to asynchronous/BSP; is it worth it for the 
      moderate speedup? **Update Thanks to the authors for their 
      clarifications and additions. I think these are reasonable arguments and 
      resolve my [very limited] qualms.