## 5 Unknown Number of Processes Multichannel Naming with Beeps
```
\(t\gets 1\) \(round\gets 0\) \(counter\gets 0\) \(collision\gets false\) \(reset\gets false\) \(j\leftarrow\) current group number repeat /* algorithm repeat loop */ \(range\_size\gets 2^{t}\) \(name\_\leftarrow\varnothing\) \(r_{\text{p}}\gets random(1,range\_size)\) repeat /* round loop */ if\(r_{\text{p}}=round\)then  beep /* end of round loop */ \(round\gets round+1\) \(FB\gets getChannelFeedback(j)\) if\(FB\) is beep then /* start of collision-checking segment */ \(collision\gets false\) for\(i\gets 1\) to \(arange\_size\)do ifCheck_Collision then \(collision\gets true\) \(reset\gets true\) /* end of segment */ if\(collision=false\)then \(counter\gets counter+1\) \(name\_\text{p}\leftarrow counter\) if\(name\_\text{p}=\varnothing\)then  beep \(FB\gets getChannelFeedback(j)\) until\(reset=true\) or FB is silence \(t\gets t*2\) until\(reset=false\)
```  
**Algorithm 5**Unknown Single Group Beep Naming  
Proof of Correctness and Analysis  
In this section, the correctness of the USGBN algorithm is proved. To do this, it is shown that the algorithm has a probability of success that is at least \(\frac{1}{2}\). **Theorem 4**. : _The USGBN algorithm assigns unique names to a set of anonymous processes, which has a time complexity of \(\mathcal{O}(n\log n)\) rounds and uses at most \(cn\log n\) random bits, and terminates with a high probability of success that is at least \(1-\frac{1}{2}^{\Omega(\log n)}\)._  
Proof. : In the round loop of the algorithm, a process chooses a random round from the range of rounds denoted as \(range\_size\). The value of \(range\_size\) is derived based on the following equation,  
\[range\_size=2^{t},\]where the value \(t\) denotes the \(t^{th}\) iteration of the main loop. For each beep heard during the round loop within the \(range\_size\), the Check-Collision procedure is executed \(at\) times. The probability of error is derived based on the number of times the Check-Collision procedure is executed. Therefore, two cases must be considered in which \(range\_size<n\) or \(range\_size\geq n\) where \(n\) is the number of processes. In each case, the probability of error is estimated in which a collision is not detected. From Lemma 1, the probability of failing to detect a collision is obtained as follows,  
\[\tfrac{1}{2}^{(i-1)k},\]  
where \(i\) is the number of processes, and \(k\) is the number of times the Check-Collision procedure is called. In the first case, the upper bound of failing to detect a collision is estimated when \(t=1\), which is the initial value. The probability of error is at its highest value when \(n/2\) processes choose the same round. The probability of failing to detect a collision is estimated to be at most  
\[\tfrac{1}{2}^{\alpha\frac{5}{2}}=\tfrac{1}{2}^{\Omega(n)}.\]  
Therefore, the probability of successfully assigning unique names is at least  
\[1-\tfrac{1}{2}^{\Omega(n)},\]  
which is greater than \(\tfrac{1}{2}\). When the \(range\_size\geq n\), processes have a higher chance of choosing unique rounds. Thus, the upper bound of failing to detect a collection is obtained when exactly two processes choose the same round. When the range of rounds is greater than or equal to the number of processes then \(t=\log n\). From Lemma 1, the upper bound for the probability of error is derived as follows,  
\[\tfrac{1}{2}^{\alpha\log n}=\tfrac{1}{2}^{\Omega(\log n)}.\]  
Therefore, the probability of successfully assigning unique names is \(1-\tfrac{1}{2}^{\Omega(\log n)}\geq\tfrac{1}{2}\). Thus, the USGBN algorithm assigns unique names to all processes with a probability of success that is at least \(\tfrac{1}{2}\). This concludes the uniqueness of names portion of the proof. Now, we estimate the time complexity of the algorithm to successfully assign unique names to all processes by computing the number of rounds needed. For each beep heard during an iteration of the round loop, the Check-Collision procedure is called \(at\) times. The algorithm terminates with a high probability of success when \(2^{t}\geq n\), i.e., \(t\geq\log n\).