# Blockchain-Based Decentralized Federated Learning Method in Edge Computing Environment
## 3 Methodology
### Preference-Based Stable Matching Algorithm
\tag{9}\]  
We also define an assignment matrix \(X\) to represent the matching relationship between local devices and edge servers. It is expressed by Equation (10), where \(x_{ks}\) denotes the matching relationship between device \(k\) and server \(s\), and \(x_{ks}=1\) means \(k\) is bound to \(s\), otherwise, \(k\) is not bound to \(s\). \[X=\left(x_{ks}\right)_{m=n}= \begin{bmatrix}x_{11}&x_{12}&\dots&x_{1n}\\ x_{21}&x_{22}&\dots&x_{2n}\\ \dots&\dots&\dots&\dots\\ x_{n1}&x_{m2}&\dots&x_{mn}\end{bmatrix} \;. \tag{10}\]  
The goal of the matching algorithm is to minimize of the total cost of model training, while also satisfying the constraint that the total number of local devices bound to edge server \(s\) cannot exceed its maximum number of device bindings. Therefore, we derive the optimization objective function, which is expressed by Equation (11). \[\min obj=\sum_{k=1}^{m}\sum_{s=1}^{n}\omega_{ks}*x_{ks}\;,\;\left(x_{ks}=0\; or\;1\right)\;. \tag{11}\]  
We propose a preference-based stable matching algorithm to solve the optimization objective function of cost minimization. Each local device \(k\) will establish a preference list of matching degrees for all edge servers. We use a binary \((k,s)\) to represent a match between device \(k\) and edge server \(s\). Equation (12) gives the preference function of \(k\) for \(s\), and \(P_{(k,s)}\) represents the matching degree of \((k,s)\). Equation (13) is the preference list of \(k\), i.e., \(\Gamma_{k}\). The matches are sorted in descending order of matching degree, that is, the higher the match in the list, the higher the preference. \[P_{(k,s)}=\eta E_{ks}+(1-\eta)T_{ks}\;, \tag{12}\]\[\Gamma_{k}=[P_{(k,s)},\ \ \forall s\in S]. \tag{13}\]  
Similarly, each edge server \(s\) will establish a matching preference list for all local devices, i.e., \(\Gamma_{s}\), according to the preference function \(P_{(s,k)}\). We only consider the strict partial order, that is, a local device will not have the same matching degree with two edge servers. The local device tends to match the edge server with the highest matching degree, and the edge server also tends to bind to the local device with the highest matching degree. However, in the matching process, we can only pay more attention to the needs of one side. In order to make the local device have a better experience in the training process, the matching algorithm should meet the needs of the local device as much as possible, that is, the local device has priority to match. Algorithm 1 describes the preference-based stable matching algorithm. All local devices and edge servers are initialized as unmatched. Then, all devices and servers broadcast their status information to each other, and each device and server establishes its preference lists. Each local device k sends a matching request to the edge server with the highest matching degree according to its \(\Gamma_{k}\). If the request is rejected, it sends the matching request to other edge servers again according to their preference lists. Each edge server first places all devices that it receives the matching request into its match list. If the number of devices in the match list is greater than its maximum binding number, the edge server will pre-enroll devices according to its preference list from front to back, and reject the devices with low matching degrees in its \(\Gamma_{s}\) until the number of devices in the match list equals its maximum binding number. If the number of local devices in the match list is less than the maximum binding number, all devices are reserved. Each edge server repeats updating its match list until all local devices are in the match lists of edge servers. The output matches of the algorithm are Pareto optimal [33]. The time complexity of the algorithm is \(O(nm)+O(n+m)\). ```
1:local device set \(K\), edge server set \(S\), maximum binding number of the server \(L_{s}\). 2:match list of edge servers \(N_{s}\).