CODEWITHSUNDEEP
network-programmingprobabilitydht
El Tikki
El Tikki

Reputation: 173

Circular DHT with different implementations

I had the following question in my exam:

This problem involves a circular DHT in which every peer node tracks just its predecessor and the successor. No shortcuts are available. Consider the following three constructions below. In all these three construction, the node IDs range from 0 to N − 1 and so do the key IDs. At a given time, the number of peer nodes participating in the DHT is M and this number is readily known to all peer nodes. The ‘value’ in the (key, value) pair is the set of IDs of the nodes that independently store the data of interest.

C-1: Every stored (key, value) pair (k, v) is stored at a random node (from among the ones that are online then).

C-2: Every stored (key, value) pair (k, v) is stored at a node whose ID is given by k mod M.

C-3: Every stored (key, value) pair (k, v) is stored at a node whose ID is k (if it is online) or its closest online successor (with wraparound).

(a) An online peer wants to find out a key k to get the corresponding value. What is the complexity (i.e., the big-oh O( )) of this operation in each of the three constructions. If you are not familiar with the O( ) notation, just state the average number of queries launched.

(b) An online node launches a query for key k and gets a set of two node IDs in return. What are the chances at least one of those nodes is online (such that the querying node can get the data of interest)? Provide your answer for each construction; your answer may be in terms of k, M, N, or any other parameter.

(c) What would be your (numerical) answer to above part (for each construction) if on average 30% nodes are online.

I have confusion over the answers I wrote. I want to know whether what I did is correct or not. I wrote the following answers :

a) C1: O(N) - in the case there are N nodes online

C2: O(M) - in the case the keys are from 0 to M-1

C3: O(1) - worst case node with key k is offline the next one is looked at

b) p=probability of being online

C1: 2C1 * p * (1-p) + 2C2 * p

C2: 2C1 * p * (1-p) + 2C2 * p

C3: 2C1 * p * (1-p) + 2C2 * p

c) C1 : 2C1 * 0.3 * 0.7 + 2C2 * 0.3

C2 : 2C1 * 0.3 * 0.7 + 2C2 * 0.3

C3 : 2C1 * 0.3 * 0.7 + 2C2 * 0.3

Upvotes: 1

Views: 832

Answers (1)

The.Shark
The.Shark

Reputation: 26

a) For C1 you have stated the answer for the case when M = N, this may not always hold so you should change it to O(M) since it will search all the online nodes as any one of them can hold the key at random.

C2: O(M) is correct as well as the reason you stated.

C3: this too will be O(M), as on average you are going to have to traverse the whole DHT to find the key.

b) You have used the wrong formula for the binomial theorem. The correct formula is:

nCk * p^k * (1-p) ^ (n-k)

So your answers should be:

C1: 2C1 * p * (1-p) + 2C2 * p^2

C2: 2C1 * p * (1-p) + 2C2 * p^2

C3: 2C1 * p * (1-p) + 2C2 * p^2

Also, note that here p = M/N (since M nodes online from N nodes)

c) Now p = 0.3

C1 : 2C1 * 0.3 * 0.7 + 2C2 * 0.3^2 = 0.51

C2 : 2C1 * 0.3 * 0.7 + 2C2 * 0.3^2 = 0.51

C3 : 2C1 * 0.3 * 0.7 + 2C2 * 0.3^2 = 0.51

Upvotes: 1

Related Questions