In a more involved case, Zoya may be also in the communication range of another base station, named Bastian, see Figure 1.3(a). This second base station serves as an alternative to which Zoya can connect to in order to get access to the overall wired infrastructure and the internet. But what if Basil and Bastian send the invitation packets simultaneously? Then, following the rules of the collision model, Zoya experiences collision and she does not receive anything useful. An easy fix could be to have both Basil and Bastian to be part of a the same communication infrastructure, which makes it viable to assume that they can communicate and coordinate over a wired channel and thus agree not to send the invite packets simultaneously.
However, there may be cases in which Basil and Bastian cannot coordinate through the wired connection, since, for example, they belong to networks with different owners. Hence, the problem of collision over a shared medium remains. If both Basil and Bastian go on to persistently send invitation packets over regular time intervals, then it can happen that they are synchronized in an unfortunate way. This is illustrated in Figure 1.3(b), where it can be seen that Zoya will not ever receive an invitation. One quasi-solution that Zoya might contemplate would be the following. The clocks of Basil and Bastian cannot be perfectly synchronized, so if Zoya patiently waits, at some point in the future the regular packet transmissions from Basil and Bastian will avoid overlapping. We dedicate space to this quasi-solution in order to show why is it not a usable one and thereby illustrate an important engineering point. Namely, a good algorithmic design cannot rely on randomization that is not controlled in any way by the participants in the system. Instead, the (pseudo-)random choice used in the protocol should be deliberately invoked by the participating actors in the system. In this example, imperfect synchronization is due to random deficiency in the production process of the clocks and it thus represents an uncontrolled random factor.
Let us now assume that the clocks of the two base stations are perfectly synchronized and they are both dividing the time into identical slots, as in Figure 1.3(c), where each slot is sufficient to send an invitation packet or receive a packet termed invitation_accepted from Zoya. Before the start of a slot, each base station flips a coin and decides randomly to transmit or stay silent in that slot. As shown in Figure 1.3(c), some invite packets will still collide, but some will be sent free of collision. Hence, the use of coin flipping leads to randomization of the transmission time between two invite packets. This randomization is the key to finalize the establishment of a contact, with high probability, within a reasonably short time.
1.2.2 Wireless Rendezvous without Help
Things get more complicated when the roles of the devices are not predefined. This is the situation in establishing ad hoc links between two devices that belong to the same hierarchical level, as in device-to-device (D2D) communication. For example, Zoya, Yoshi, and Xia can be three mobile phones that want to start communication, but have never communicated with each other before. The last assumption is important, since if Yoshi and Xia have already communicated in the past, they may have agreed who should be the one sending the invite packet next time they need to communicate. In the absence of such a context, it is impossible to predefine the roles. For example, if Zoya and Yoshi are predefined to be the ones sending invite packets, while only Xia is waiting to receive them, then Zoya and Yoshi cannot establish a link between them. The problem of first contact when devices are symmetric is exacerbated by the half-duplex nature of devices: if Zoya and Yoshi are continuously sending invitations to each other, then neither of them is able to receive the invitation from the other one.
Coin flipping again helps to resolve this situation. Let us assume that Zoya and Yoshi have a common time reference for a slotted channel, as in the case with Basil and Bastian. Achieving the required synchrony is harder to justify in this case, compared to the example in which a device establishes connection with a base station. Nevertheless, for the purpose of this example, one can assume that both Zoya and Yoshi have GPS receivers that can be used for clock synchronization. Let both Zoya and Yoshi be quiet in the
But what if Zoya and Yoshi are not synchronized in using the slotted channel; can that help or make things even more difficult? In fact, the synchronous case can be seen as the worst case: if both Zoya and Yoshi decide to transmit in a certain slot, then their packets are completely overlapping. On the other hand, the lack of synchronism can be helpful in breaking the symmetry between Zoya and Yoshi. For example, we can have the situation in which both Zoya and Yoshi decide to transmit, but the transmission slot of Yoshi starts slightly later than Zoya's slot. Yoshi starts to receive the invite packet and postpones his transmission in order to complete the reception of Zoya's packet. In this example, Yoshi adjusts its clock to Zoya and, after the invite packet is received, Yoshi sends back a reply using Zoya's slot timing. It can be seen that, when the devices are not in synchrony, the symmetry can be broken without using randomization, as some form of randomization is already embedded in the asynchronism. However, recalling our discussion on a proper protocol design and controlled randomness, asynchronism can facilitate the rendezvous protocol, but it should not be the definitive solution; the protocol should always have the opportunity to rely on an intentional randomized choice.
Through the problem of first contact and link establishment, we have introduced randomization as the key idea used in breaking the