## 4 Known Number of Processes Multichannel Naming with Beeps
The authors in [20] also proved the following theorem, which we refer to regarding the correctness of the SGBN algorithm. **Theorem 1**. : _The SGBN algorithm is guaranteed to terminate, and on termination, it assigns unique names to all processes that require at most \(cn\log n\) rounds and uses at most \(cn\log n\) random bits with a probability of success at least \(1-\left(\frac{1}{2}^{a\left(n\log n-\log n\right)}\right)^{m}\)._  
Based on Lemma 1, the time complexity of the SGBN algorithm is computed. At most \(3n\) round selections are needed before all processes are assigned unique names. For each round selection, \(\alpha\log n\) Check-Collision procedure calls are made, and each call takes exactly two rounds. Therefore, the time complexity is \(\mathcal{O}(n\log n)\) rounds because the algorithm requires at most \(6\,\alpha\,n\log n\) rounds. Thus, at most, \(3\,\alpha\,n\log n\) Check-Collision procedure calls are made, which implies that the algorithm uses at most \(cn\log n\) random bits. The SGBN algorithm continues repeating the procedure of choosing unique rounds for all processes until they are all assigned unique names in the range \((1,n)\) and \(counter=n\). Next, the correctness of the second part of the algorithm is proved, which consists of the TN algorithm and the MCBN algorithm. First, the correctness of the TN algorithm is demonstrated in which each group is notified about the termination of the SGBN algorithm by every other group. We begin with the initial step when the SGBN algorithm terminates for group \(j\), and the process with the lowest name is designated as the leader for the group. Afterward, it is demonstrated that exactly one process is assigned as a leader for each group \(j\). From Theorem 1, all processes are assigned unique names from the range \((1,n)\). Thus, a process knows that it is the leader of its group when its name is \(1\). Assuming that two or more processes are assigned as group leaders, it would imply they are assigned the same name of \(1\). This contradicts Theorem 1, which states that when the algorithm terminates all processes are assigned unique names. Therefore, exactly one process is assigned as a leader for group \(j\). **Theorem 2**. : _The Termination Notification algorithm terminates after \(\mathcal{O}(n\log n)\) rounds and when it terminates, the processes in all groups are notified about the termination of the SGBN algorithm._  
Proof. : It is shown that the leader of each group \(j\) for all \(j\in(1,k)\) obtains the knowledge about the termination in all other groups. First, we begin with the initial state where the SGBN algorithm has terminated for group \(h\), \(1\leq h\leq k\). Then, the leader process of group \(j\) begins executing the TN algorithm on which the leader keeps counting the number of beeps heard on Channel \(0\) for every \(k\) rounds. The leader process of group \(j\) beeps on Channel \(0\) during the \(j^{th}\) round. When the total number of beeps is less than \(k\), the same process is repeated for every \(k\) rounds. When the leader process of group \(j\) has heard \(k\) beeps during the current cycle, this implies that group \(j\) has finished executing the TN algorithm. Because the leader process of group \(j\) has heard \(k\) beeps, it implies that all other processes in other groups have also heard \(k\) beeps during the current cycle of \(k\) rounds. Thus, the algorithm terminates for all groups, and when it terminates, the processes of each group obtain knowledge regarding the termination of the SGBN algorithm in all other \(k-1\) groups. Next, the time required for the TN algorithm to terminate is analyzed. Assuming that group \(h\) has finished the execution of the SGBN algorithm and began executing the TN algorithm, the number of times the TN algorithm repeats is estimated. From Theorem 1, the SGBN algorithm has a time complexity of \(\mathcal{O}(n\log n)\) rounds, which implies that the leader process of group \(j\) must wait for at most \(\mathcal{O}(n\log n)\) rounds.