## 7 The TFL-Free Property
### Algorithm for TFL-Free SDN Updating
#### 7.2.1 Algorithm Overview
The difference is at the level of the communicating processes and of the type of data for sending. Switch message/packet reception: From the point of view of the receiver \(rp_{j}\) (see Algorithm 3), an \(mp\) piggybacks delivery constraints encapsulated into \(Cl_{mp}\), that is messages that must be delivered to \(p_{j}\) before \(mp\). Note that there is a distinction between the reception of a message \(mp\) (see Line 2) and its delivery (see Line 4). The delivery of \(mp\) to a process \(p_{j}\) implies that the message in question was received and all previous delivery constraints on \(p_{j}\) were satisfied (see Line 3). Thus, once the delivery constraints are satisfied, \(mp\) is delivered to \(p_{j}\) (see Line 4), and what follows is updating the control information of the receiver process \(p_{j}\). Then, \(p_{j}\) updates its \(Delivery_{j}\) matrix, indicating that the message sent from \(p_{i}\), whose sequence number is equal to \(t_{mp}\), was already delivered to \(p_{j}\) (see Line 5). The \(Delivery_{j}\) matrix is also updated with respect to the messages \(mps\) delivered to process \(p_{i}\) (see Line 6). After the delivery of \(mp\), \(p_{j}\) updates a new delivery constraint for future messages sent from \(p_{j}\). Therefore, \(Cl_{j}[j]\) is updated by adding \((i,t_{mp})\), using the \(\cup_{max}\) operator as a new potential direct dependency on subsequent messages sent from \(p_{j}\) and by deleting older direct dependencies (transitive dependencies), using the \(-_{max}\) operator (see Line 7), which were already satisfied. The operator \(\cup_{max}\) (see Algorithm 4) ensures that if there are multiple constraints corresponding to a sender process, the most recent constraint is selected [6]. The \(-_{max}\) operator (see Algorithm 5) deletes the delivery constraints already known to be satisfied (T2) from the current set of message delivery constraints (T1) [6]. Furthermore, and to maintain the causality property, a message sent by a process \(p_{k}\) to \(p_{j}\), whose send event is causally dependent on messages sent by \(p_{i}\) to \(p_{j}\), should be delivered to \(p_{j}\) only after the \(n^{\text{th}}\) message sent by \(p_{i}\) to \(p_{j}\). Thus, for all processes \(p_{k}\), except the ones for the sender and receiver, \(Cl_{i}[k]\) is updated by adding the delivery constraints piggybacked by \(Cl_{mp}\) (see Line 8). As we have mentioned, the \(Delivery\) matrix is used for garbage collection to reduce the communication overhead when ensuring the causal ordering of messages. Therefore, based on the \(Delivery_{j}\) matrix of process \(p_{j}\), \(Cl_{j}\) is updated in such a way that it contains only the recent delivery constraint needed for the delivery of future messages (see Lines 9 to 12). ```
1: Boolean change, set of tuples \(T1\), set of tuples \(T2\), set of tuples \(T\)
2:change := true
3:\(T:=T1\cup T2\) (\(T1\) and \(T2\) contain the delivery constraints)
4:while (change) {
5:change := false
6:if\((i,x)\in T\) and \((i,y)\in T\) and \((x<y)\)
7:{\(T:=T-\{(i,x)\}\)
8:change := true } }
```

**Algorithm 4** : The operator \(\cup_{max}\): (\(T1\cup_{max}T2\)). ```
1:Boolean change, set of tuples \(T1\), set of tuples \(T2\), set of tuples \(T\)
2:change := true
3:\(T:=T1\cup T2\) (\(T1\) and \(T2\) contain the delivery constraints)
4:while (change) {
5:change := false
6:if\((i,x)\in T\) and \((i,y)\in T2\) and \((x\leq y)\)
7:{\(T:=T-\{(i,x)\}\)
8:change := true } }
```

**Algorithm 5** : The operator \(-_{max}\): (\(T1-_{max}T2\)). ```
1:Boolean change, set of tuples \(T1\), set of tuples \(T2\), set of tuples \(T\)
2:change := true
3:\(T:=T1\)
4:while (change) {
5:change := false
6:if\((i,x)\in T\) and \((i,y)\in T2\) and \((x\leq y)\)
7:{\(T:=T-\{(i,x)\}\)
8:change := true } }
```

**Algorithm 6** : The operator \(-_{max}\): (\(T1-_{max}T2\)). ### Proof of Correctness

In the previous subsection, we presented an adaptation of a causal ordering algorithm as a solution for the TFL problem. We now demonstrate that the proposed algorithm is TFL-free.