  Synchronous local stochastic gradient descent (local SGD) suffers from some
workers being idle and random delays due to slow and straggling workers, as it
waits for the workers to complete the same amount of local updates. In this
paper, to mitigate stragglers and improve communication efficiency, a novel
local SGD strategy, named STSyn, is developed. The key point is to wait for the
$K$ fastest workers, while keeping all the workers computing continually at
each synchronization round, and making full use of any effective (completed)
local update of each worker regardless of stragglers. An analysis of the
average wall-clock time, average number of local updates and average number of
uploading workers per round is provided to gauge the performance of STSyn. The
convergence of STSyn is also rigorously established even when the objective
function is nonconvex. Experimental results show the superiority of the
proposed STSyn against state-of-the-art schemes through utilization of the
straggler-tolerant technique and additional effective local updates at each
worker, and the influence of system parameters is studied. By waiting for
faster workers and allowing heterogeneous synchronization with different
numbers of local updates across workers, STSyn provides substantial
improvements both in time and communication efficiency.
