Socially Optimal Mechanism Design for Relay-Assisted Asynchronous Federated Learning

Federated learning (FL) has been extensively applied in industrial cyber-physical systems (ICPSs) to develop powerful models for complex industrial tasks (e.g., fault diagnosis), while safeguarding industrial data confidentiality. Asynchronous federated learning (AFL) effectively mitigates the straggler issue in the synchronous paradigm by aggregating client models in a first-come-first-served manner. Proper client selection is crucial for achieving efficient model training in AFL. A widely adopted model for implementing client selection in AFL is multi-armed bandit (MAB), which models client selection as arm pulling. Existing MAB-based client selection schemes overlook practical scenarios where direct client-server communications are unfavorable or unavailable (for example, in ICPSs such as mines, where communication infrastructure is underdeveloped, direct client-server communication is often unreliable or even unfeasible). In such cases, the server needs to incentivize self-interested relays to perform arm-pulling actions, including selecting the right client and relaying the communication from the selected client to the server. This paper proposes the first framework of incentivized online client selection for AFL. The design and optimization of such a framework involve significant challenges due to the tight coupling between unknown client behavior and private relay cost. To circumvent this challenge, we adopt the dual-based method and construct a special Lagrangian function that incorporates client behavior learning and relay cost revelation, and utilize it to design a socially-optimal mechanism for the framework. Our mechanism satisfies several desirable properties, including voluntary participation, incentive compatibility, relay utilization fairness, and client participation fairness. The proposed mechanism achieves the same asymptotic performance as the state-of-the-art benchmark that requires additional information. Furthermore, our analysis reveals that more available relays bring our mechanism closer to the theoretical upper bound of social performance. Numerical results demonstrate that our proposed mechanism achieves up to 85% and 99% of the social welfare obtained by the benchmarks.