on the superimposed RF signal,recovering each update,and to compress the sparse update of each client,such that they averaging them,as shown in Fig.1.We denote our solution are aligned and can be efficiently aggregated by PhyArith. as Physical-Layer Arithmetic (PhyArith),where the clients The main contributions are summarized as follows:(1) encode their local updates into aligned digital sequences which We show that even if not applying pre-channel-compensation, are converted into RF signals for sending to the server simulta- the superimposed RF signal can be exploited to efficiently neously,and the server directly recovers the exact summation aggregate updates,without incurring any aggregation error. of these updates from the superimposed RF signal through a (2)Based on full digital operation,we design the client-side customized decoder. updates encoding process of PhyArith,such that it can be applied on commodity 802.11 devices,and their summation can be reliably recovered and verified.We also design its Client server-side decoding process where a customized sum-product Client Update algorithm is provided to directly recover the summation of a ，1▣ large number of updates.(3)PhyArith can be integrated with Client Updaterl- other updates compression methods.Simulation results show RE sic Process of clients that Phy Arith further improves the communication efficiency Process of server by 1.5 to 3 times for training LeNet-5,compared with the solutions which apply quantization/sparsification to compress updates,and aggregate them via MUD. Uptim- II.RELATED WORK 黑器 A.Quantization and Sparsification Averaged update Summation of updates Updates quantization and sparsification are the two main approaches to overcome the communication bottleneck in decentralized learning.Updates quantization was first pro- posed in [5],where elements not less than zero are encoded Fig.1.Recovery of averaged update based on MUD and PhyArith as bit 1,and those less than zero are encoded as bit 0. Following such 1-bit quantization,subsequent work like [8] For this purpose,three main challenges should be well [9]introduce multilevel updates quantization,so as to balance addressed.The first challenge is,how to encode each update at the communication efficiency and updates accuracy.Updates the client with commodity devices based on full digital opera- sparsification was first proposed in [6],where only elements tion,such that PhyArith can conveniently and reliably recover with large absolute value are encoded using 1-bit quantization. their exact summation.and effectively verify its correctness.To and sent out along with their associate index.Following this address this challenge,we encode updates into aligned digital approach,various sparsification methods,like sending fixed sequences by taking two's-complement representation [15]as proportion of large elements [7],are proposed. source codes,and systematic low-density parity check(LDPC) codes [16]as channel codes,such that the addition and B.AirComp subtraction operations during aggregation can be unified,and Recent AirComp based work focus on leveraging the su- error correction capability can be provided.We also append perposition of RF signal to aggregate client-side updates. the cyclic-redundancy-checksum(CRC)[17]with each update, Specifically,[12][13]study performing power control and such that its linear property can be exploited to verify the client selection to align the signal power received at the server correctness of the directly recovered summation.The second and avoid incurring serious aggregation error.[10]studies challenge is,how to directly recover the exact summation aggregating updates during wireless networks with power and of updates at the server,which is equipped with multiple bandwidth limitations,based on coded digital transmission in antennas,based on the superimposed RF signal of these different time-frequency resources,and uncoded analog trans- encoded updates emanating from a large number of different mission in the same time-frequency resource,i.e.,performing clients.To address this challenge,from the superimposed AirComp.It is also worth noting that although recent AirComp RF signal,we propose a sum-product algorithm [18]derived related work are all based on uncoded analog transmission,its polynomial time complexity decoder to directly obtain the original idea appeared in [19],which relies on lattice codes marginal probability mass function(PMF)of the summation of to achieve reliable over-the-air computation.However,it also updates.By maximizing the obtained PMF,we can recover the assumes no fading channel,which can not be directly applied summation,verify its correctness,and update the global model. on commodity devices at the client-side.And at the server- And the third challenge is,how to integrate PhyArith with side,it lacks practical efficient decoding approach. those updates compression methods like sparsification,where the client-side updates are not necessarily aligned due to C.MUD compression.To address this challenge,we adopt compressed- Different from AirComp,the conventional approach to sensing here by using a shared underdetermined sensing matrix deal with the superimposed RF signal is multiuser detectionon the superimposed RF signal, recovering each update, and averaging them, as shown in Fig. 1. We denote our solution as Physical-Layer Arithmetic (PhyArith), where the clients encode their local updates into aligned digital sequences which are converted into RF signals for sending to the server simulta￾neously, and the server directly recovers the exact summation of these updates from the superimposed RF signal through a customized decoder. Update|V |−1 Update1 Update0 MUD decoder Update∗ |V |−1 Update∗ 1 Update∗ 0 Averaged update PhyArith decoder Averaged update Summation of updates PhyArith based solution MUD based solution Propagate Process of server Process of clients · · · · · · · · · RF signal Superimposed Client RF signal Client Client · · · Fig. 1. Recovery of averaged update based on MUD and PhyArith For this purpose, three main challenges should be well addressed. The first challenge is, how to encode each update at the client with commodity devices based on full digital opera￾tion, such that PhyArith can conveniently and reliably recover their exact summation, and effectively verify its correctness. To address this challenge, we encode updates into aligned digital sequences by taking two’s-complement representation [15] as source codes, and systematic low-density parity check (LDPC) codes [16] as channel codes, such that the addition and subtraction operations during aggregation can be unified, and error correction capability can be provided. We also append the cyclic-redundancy-checksum (CRC) [17] with each update, such that its linear property can be exploited to verify the correctness of the directly recovered summation. The second challenge is, how to directly recover the exact summation of updates at the server, which is equipped with multiple antennas, based on the superimposed RF signal of these encoded updates emanating from a large number of different clients. To address this challenge, from the superimposed RF signal, we propose a sum-product algorithm [18] derived polynomial time complexity decoder to directly obtain the marginal probability mass function (PMF) of the summation of updates. By maximizing the obtained PMF, we can recover the summation, verify its correctness, and update the global model. And the third challenge is, how to integrate PhyArith with those updates compression methods like sparsification, where the client-side updates are not necessarily aligned due to compression. To address this challenge, we adopt compressed￾sensing here by using a shared underdetermined sensing matrix to compress the sparse update of each client, such that they are aligned and can be efficiently aggregated by PhyArith. The main contributions are summarized as follows: (1) We show that even if not applying pre-channel-compensation, the superimposed RF signal can be exploited to efficiently aggregate updates, without incurring any aggregation error. (2) Based on full digital operation, we design the client-side updates encoding process of PhyArith, such that it can be applied on commodity 802.11 devices, and their summation can be reliably recovered and verified. We also design its server-side decoding process where a customized sum-product algorithm is provided to directly recover the summation of a large number of updates. (3) PhyArith can be integrated with other updates compression methods. Simulation results show that PhyArith further improves the communication efficiency by 1.5 to 3 times for training LeNet-5, compared with the solutions which apply quantization/sparsification to compress updates, and aggregate them via MUD. II. RELATED WORK A. Quantization and Sparsification Updates quantization and sparsification are the two main approaches to overcome the communication bottleneck in decentralized learning. Updates quantization was first pro￾posed in [5], where elements not less than zero are encoded as bit 1, and those less than zero are encoded as bit 0. Following such 1-bit quantization, subsequent work like [8] [9] introduce multilevel updates quantization, so as to balance the communication efficiency and updates accuracy. Updates sparsification was first proposed in [6], where only elements with large absolute value are encoded using 1-bit quantization, and sent out along with their associate index. Following this approach, various sparsification methods, like sending fixed proportion of large elements [7], are proposed. B. AirComp Recent AirComp based work focus on leveraging the su￾perposition of RF signal to aggregate client-side updates. Specifically, [12] [13] study performing power control and client selection to align the signal power received at the server and avoid incurring serious aggregation error. [10] studies aggregating updates during wireless networks with power and bandwidth limitations, based on coded digital transmission in different time-frequency resources, and uncoded analog trans￾mission in the same time-frequency resource, i.e., performing AirComp. It is also worth noting that although recent AirComp related work are all based on uncoded analog transmission, its original idea appeared in [19], which relies on lattice codes to achieve reliable over-the-air computation. However, it also assumes no fading channel, which can not be directly applied on commodity devices at the client-side. And at the server￾side, it lacks practical efficient decoding approach. C. MUD Different from AirComp, the conventional approach to deal with the superimposed RF signal is multiuser detection