Skip to content

Latest commit

 

History

History
36 lines (24 loc) · 1.6 KB

README.md

File metadata and controls

36 lines (24 loc) · 1.6 KB
Raw

Paper

Wu, W., He, L.*, Lin, W., Mao, R., & Jarvis, S. (2021). SAFA: a Semi-Asynchronous Protocol for Fast Federated Learning with Low Overhead. IEEE Transactions on Computers (TC). vol. 70, no.5, pp. 655-668.

Env

  • Python 3.7.3
  • Pytorch 1.1.0
  • PySyft 0.1.2 # optional
  • numpy 1.16.4

SAFA Protocol

  • Lag-tolerant model distribution:

            w_k(t) = W(t-1), if k in Union_(v=t-1){Mv}           // Latest clients will sync. with server
        w_k(t) = W(t-1), if k in Union_(v<t-tao){Mv}         // Deprecated clients are forced to sync. 
        w_k(t) = w_k(t-1), if k in Union_(t-tao<=v<t-1){Mv}  // Moderately straggling clients stay async.

  • Local update:

            w_k(t) = clientUpdate(k, w_k(t)), if k in M-K(t)     // post-training w_k in round t

  • Pre-aggregation Cache update:

            w*_k(t) = w_k(t), for k in P                         // Update entries of picked clients
        w*_k(t) = W(t-1), for k in Union_(v<t-tao){Mv}       // Deprecated entries are replaced

  • SAFA aggregation:

            W(t) = sum_(k in M){n_k/n * w*_k(t)}

  • Post-aggregation Cache update:

            w*_k(t+1) = w_k(t), for k in Q                       // undrafted updates bypass round t
        w*_k(t+1) = w*_k(t), for k in P                      // already updated in pre-aggregation update 
        w*_k(t+1) = w*_k(t), for k in K                      // no update for crashed clients

where M is the client set, Mv is the version-v client set, P is picked set, Q is undrafted set, K is the crash set, tao denotes lag tolerance.