[News]

News: Welcome to The Oktave Forum.

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

[Update:]

Am afraid I don't get this either. What are '+' and '-' in terms of network operations?

Let's say we have a network of 13 nodes, with each node having the list P = {1, 3, 9}. Let's say every node connects to a set of other nodes in the following manner: a node with label n_i will connect to the node with label n_i + P_i; since edges are undirected, n_i is also connected to n_i + p_i*; thus, each node will connect to a maximum of 2*|P| other nodes. The operations are modulo n, of course.

Now, every node knows its direct connections. It also knows that all other nodes have an edge each to their corresponding +/- P_ith nodes. In our specific example, node 1 is connected to 2, 13, 4, 11, 10 and 5. If we want to reach node 7 from node 1, node 1 will compute it as folows: 5 + (3 - 1) or, better still, 10 - (3). Because it knows that its neighbours have connections to nodes that are 1, 3 or 9 numbers away from them.

Update:
* I meant, n_i is also connected to n_i - p_i

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

t's turning out to be the series 3n

Pmin = {1,3,9,27,81...} and max number that can be generated would be simply sum of all the elements of Pmin.

That's right! For a given n, the k elements of Pmin are, P1 = 3⁰, P2 = 3¹, ..., Pk = n - summation(P1 through Pk-1) (Or Pk = 3^k-1, if n is the biggest number for a given k).

If that is the case, then how is Pmin for 10 = {1,3,6}? 6 is not a power of 3.

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

Let's say we have a network of 13 nodes, with each node having the list P = {1, 3, 9}. Let's say every node connects to a set of other nodes in the following manner: a node with label n_i will connect to the node with label n_i + P_i; since edges are undirected, n_i is also connected to n_i + p_i*; thus, each node will connect to a maximum of 2*|P| other nodes. The operations are modulo n, of course.

Sorry, I'm still not getting the idea.. 

What is P_i in the earlier expression? Is it the i^th element of P? (If P is considered as an ordered tuple, of course).

If so, how is P_i related to n_i? I believe the interval range for i in n_i is 0-12 or 1-13. But the range for i in P_i is only 1-3.

I'm quite stuck here and could not proceed further.

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

t's turning out to be the series 3n

Pmin = {1,3,9,27,81...} and max number that can be generated would be simply sum of all the elements of Pmin.

That's right! For a given n, the k elements of Pmin are, P1 = 3⁰, P2 = 3¹, ..., Pk = n - summation(P1 through Pk-1) (Or Pk = 3^k-1, if n is the biggest number for a given k).

If that is the case, then how is Pmin for 10 = {1,3,6}? 6 is not a power of 3.

As I said, for a given k, there is a maximum n up to which you can construct all numbers using the k elements in Pmin. And the Pmin for this maximum n is, Pmin = {3⁰, 3¹, 3², ..., 3^(k-1)}.

*However*, in the general case, the Pmin starts as 3⁰, 3¹ etc.. But the last element of Pmin might not be a power of 3. It will be this - Pk = n - summation(all previous elements of Pmin). So, it is basically "whatever is left" after you have divided the number into sums of powers of 3.

So, for 10, Pmin = {1, 3, 10 - (1 + 3)} = {1, 3, 6} or for 51, Pmin = {1, 3, 9, 27, 11}

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

The following is an explanation for the 3^k series. This is not an exact reasoning, but an attempt to show how it works.

Let us say we want to cover numbers from 1 through n. Let us not specify n. Let us simply say we want to generate the largest n possible using k numbers that are elements of Pmin.

Let's begin at the beginning.

When k = 1, We can only have Pmin = {p₁ = 1}, and the numbers covered, C = {1}

When k = 2, let's say p₂ is the next element. What should it be? We know that using p₁ and p₂, we can construct 2 more numbers. In addition, p₂ itself will be another number it will cover. Now, since we want to maximize the numbers that are covered, we don't want a combination of p₁ and p₂ to cover a number that is already covered by p₁. So, on the number line, p₂ should be as far away from p₁ as to cover all numbers after p₁to its left, and itself, plus another p₁ numbers to its right.

More simply, p₂ - (the biggest number p₁ has covered) = (the biggest number p₁ has covered) + 1
Specifically, p₂ - 1 = 2. Thus, p₂ = 3.

When k = 3, we need to find p₃. Now, the set {1, 3} can cover up to 4. So, we can cover from p₃ - 4 through p₃ + 4. Again, to maximize this, we need to place p₃ optimally on the number line. So, p₃ should be placed 5 slots away from p₂. So, p₃ is 9. Another way to look at it is this: p₃ covers 4 numbers to its left + it covers itself + it covers 4 numbers to its right. Thus, 9.

When k = 4, p₄ = 13 + 1 + 13 = 27  [13 = 1 + 3 + 9]

Similarly, p₅ = 40 + 1 + 40 = 81   [40 = 27 + 13]
p₆ = 121 + 1 + 121 = 243   [121 = 81 + 40]
p₇ = 364 + 1 + 364 = 729   [364 = 243 + 121]
p₈ = 2187 etc..

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

Sorry, I'm still not getting the idea.. 

Okay, guess I am not explaining properly. Plus I mixed up notations. So ignore the previous one. Let me try here.

Let us say there are n nodes, N = {1, 2, ..., n}. An element N_i is any node in this list.

We have a P_min = {p₁, p₂, ..., p_k}. We have k elements and P_j is any element in this set.

Now, P_min is a skip-list similar to the Chord skip-list. In case of Chord, every node connects to nodes that are {2, 4, 8, ..., 2^{log n}}, skips away from itself. In our case, every node connects to nodes that are {p₁, p₂, ..., p_k}, skips away from itself. Since, the edges are undirected, a node N_i is effectively connected to nodes N_i +/- P_j (1 <= j <= k).

In the specific example, where n = 13, and P_min = {1, 3, 9}, node 1, for example, is connected to 1 + 1 = 2, 1 - 1 = 13 (this is modulo 13), 1 + 3 = 4, 1 - 4 = 11, 1 + 9 = 10, 1 - 9 = 5. The other nodes are also similarly connected.

Every node knows its direct connections. It also knows that all other nodes use P_min to make connections. So, it can work out a routing scheme that is akin to constructing a number using P_min. For example, I want to reach node 7 from node 1. So, 7 = (1 + 9) - (3) = 10 - 3. Node 1 is connected to 10. And it knows that 10 is connected to 7 as it is 3 numbers away from it. Similarly, 6 = (5) - (1), 8 = 5 + 3 or 11 - 3 and so on.

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

Ah! I think I get the idea now.. Somewhat similar to the undirected version of deBruijn graphs. Will analyze in more detail later when time permits.