## 4 Known Number of Processes Multichannel Naming with Beeps
```
totalGroups \(\leftarrow\) number of groups \(name\leftarrow\) current name of the process \(j\leftarrow\) current group number \(n\leftarrow\) the number of processes for group \(j\) totalBeeps \(\gets 0\) round \(\gets 1\) \(FB\leftarrow\varnothing\) /* waiting for \(k\) beeps to be heard */ repeat if\(round=j\)then  BeepOnChannel(0) \(FB\gets getChannelFeedback(0)\) if\(FB\) is beep then \(totalBeeps\gets totalBeeps+1\) \(round=round+1\) if\(round=(k+1)\)then \(round=1\) \(totalBeeps\gets 0\) until\(totalBeeps=k\)
```  
**Algorithm 3**Termination Notification  
The second part of the algorithm begins when each group of processes detects the termination condition. In this part of the algorithm, all processes execute the Multi Group Renaming (MGR) algorithm shown in Algorithm 4. The goal is to make the set of all names for all processes form a consecutive set of unique names starting from 1 until \(N\). The previously designated leaders communicate with other processes in other groups. The leader of group \(j\) sends the total number of processes \(n_{j}\) to the processes in the next group, i.e., group \(j+1\). The procedure of sending the number of processes \(n_{j}\) is performed by encoding the number to its binary form: representation \(Binary(n_{j})\). The binary representation is then sent to group \(j+1\) through a special encoding of bits called _binary beep encoding_. Sending a single bit requires a pair of rounds, such that a single beep in the first round represents 0, whereas a single beep in the second round represents 1 (similar to Morse code). The end of a binary number is encoded in a pair of rounds with a beep in the first and second rounds. All processes that are members of group \(j+1\) receive the number of processes from the previous group and update their assigned names as follows,  
\[P_{id}=P_{id}+n_{j},\]  
where \(P_{id}\) is the current name of the process \  
Proof of Correctness and Analysis  
In this section, we prove the correctness of both parts of the MCBN algorithm and analyze the time complexity and the number of random bits needed. The procedure for the SGBN algorithm is represented as the operation of assigning a process to a random round until it is singleton. A process is a singleton when no other processes have selected the same round. Checking for a collision in the selected round requires a maximum of \(\alpha\log n\) calls to the Check-Collision procedure. After \(i\) processes execute the Check-Collision procedure \(k\) times, then the probability of failing to detect a collision is \(\frac{1}{2}^{(i-1)k}\). Proof. : There are \(i\) processes calling the Check-Collision procedure. Each call consists of two rounds. For each call, two possibilities exist for the outcome of choosing which round to beep in, which is determined by a random coin flip. Thus, a process can either beep in the first or second round, but not both. If the outcome of the first process is denoted as \(R\), then the probability of another process choosing \(R\) is \(\frac{1}{2}\). A collision is not detected when all remaining \(i-1\) processes choose the same round \(R\). When the number of processes \(i\) is equal to \(1\), the probability of detecting a collision is \(0\), because no other processes call the Check-Collision procedure. Otherwise, the probability of not detecting a collision when \(i\) processes call the Check-Collision procedure is \(\frac{1}{2}^{(i-1)}\), given \(i\geq 2\). To derive the probability of \(k\) different calls of the Check-Collision procedure, the probability is multiplied \(k\) times. Therefore, the probability of failing to detect a collision for \(k\) Check-Collision procedure calls is \(\frac{1}{2}^{(i-1)k}\). Next, the number of times a process chooses a random round before getting a name is estimated. We recall the result from [20], which states:  
The number of times a process chooses a random round is at most \(3n\) with a probability of \(e^{\frac{-n}{4}}\).