Asymmetric Oblivious Blind Rendezvous Algorithms
In this chapter, we present asymmetric algorithms for the oblivious blind rendezvous problem. In the setting, we fix Alg as: $$\begin{aligned} RS = \end{aligned}$$ (12.1)where \(Time \in \{Syn, Asyn \}\) , \
- PDF / 199,996 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 36 Downloads / 174 Views
Asymmetric Oblivious Blind Rendezvous Algorithms
Abstract In this chapter, we present asymmetric algorithms for the oblivious blind rendezvous problem. In the setting, we fix Alg as: RS =< Alg-AS, Time, Port, ID, Obli >
(12.1)
where Time ∈ {Syn, Asyn}, Por t ∈ {Port − S, Port-AS}, and I D ∈ {Non-Anon, Anon}. Similar to designing asymmetric algorithms for the blind rendezvous problem in Chap. 6, the users’ identifiers (IDs) could be used to break symmetric situations in distributed rendezvous algorithms, but they do not play the vital role, since many works do not assume the existence of distinct IDs. Therefore, we design rendezvous algorithms for 4 different rendezvous setting: Synchronous and Port-Symmetric, Asynchronous and Port-Symmetric, Synchronous and Port-Asymmetric, and Asynchronous and Port-Asymmetric, regardless of the choice of I D from {N on-Anon, Anon}. In Sect. 12.1, we present efficient algorithms for port-symmetric scenarios, where the users could start synchronously or asynchronously. In Sect. 12.2, we handle the synchronous and port-asymmetric situation, and the rendezvous algorithms for asynchronous and port-asymmetric situation are provided in Sect. 12.3. Finally, we summarize the chapter in Sect. 12.4.
12.1 Port-Symmetric Rendezvous Consider two users u a and u b , and suppose their available port sets are Ca , Cb ⊆ U respectively. We introduce rendezvous algorithms for port-symmetric rendezvous for both synchronous users and asynchronous users, in the following setting: RS =< Alg-AS, Time, Port-S, ID, Non-Obli >
(12.2)
where Time can be either Syn or Asyn.
© Springer Nature Singapore Pte Ltd. 2017 Z. Gu et al., Rendezvous in Distributed Systems, DOI 10.1007/978-981-10-3680-4_12
141
142
12 Asymmetric Oblivious Blind Rendezvous Algorithms
Algorithm 12.1 Fixed Port Accessing Algorithm 1: Denote set of available ports as C = {c(1), c(2), . . . , c(k)} where k = |C|; 2: Choose a random number s ∈ [1, k]; 3: Access port c(s) all the time;
Algorithm 12.2 Oblivious Sequential Accessing Algorithm 1: 2: 3: 4: 5: 6: 7:
Denote time t := 1, the user’s port set as C ⊆ U ; Denote k := |C|, and C = {c(1), c(2), . . . , c(k)} while Not rendezvous do Let x := (t − 1)%k + 1; Access port c(x) in time t; t := t + 1; end while
We introduce two different algorithms. The first one is called the Fixed Port Accessing (FPA) algorithm, which is described in Algorithm 12.1. In the algorithm, the user labels the available channels as: C = {c(1), c(2), . . . , c(k)}
(12.3)
and it chooses a random number s in the range [1, k], where k is the number of all available ports. Then, it will access port c(s) all the time. The second algorithm is called the Oblivious Sequential Accessing (OSA) algorithm which is described in Algorithm 12.2. In the algorithm, the user accesses the ports in a sequential way just like the Sequential Accessing Algorithm in Chap. 6. The difference is: the user does not know the global label of each port, and it has to access the port sequentially by its local labels. Consider two users
Data Loading...
