Key distribution

The distribution of responsibilities in the P-Grid network is critical. Without a well performing algorithm for key and data distribution the efficient search algorithm described later becomes useless. Each peer in the P-Grid network is responsible for a specific key prefix. The length of this prefix grows as the peer communicates with other peers in the network.

Initially all peers are responsible for everything, or at least they think they are. If figure fig:pgridconnect describes a set of hosts that are all initially responsible for everything and the order of communication is determined by the numbered arrows. Table tbl:pgridconnect then shows how the prefixes and reference table that each host is responsible for could change during a sequence of exchanges.

Illustration 4.2: P-Grid network connection establishment order

Table 4.1: Key responsibility distribution in P-Grid

p	Step 1		Step 2		Step 3
A	0	1 -> B	0	1 -> B	01	1 -> BF 00 -> C
B	1	0 -> A	1	0 -> A	11	0 -> AE 10 -> D
C	0	1 -> F	0	1 -> F	00	1 -> FB 01 -> A
D			1	0 -> E	10	0 -> EAC 11 -> B
E			0	1 -> D	0	1 -> D
F	1	0 -> C	1	0 -> C	11	0 -> CEA 10 -> D
G			1	0 -> C	10	0 -> CEA 11 -> F
p	Step 4		Step 5
A	01	1 -> BF 00 -> C	01	1 -> BFD 00 -> C
B	11	0 -> AEC 10 -> D	11	0 -> AEC 10 -> D
C	00	1 -> FB 01 -> A	00	1 -> FB 01 -> A
D	10	0 -> EAC 11 -> B	10	0 -> EAC 11 -> B
E	0	1 -> D	00	1 -> DBF 01 -> A
F	11	0 -> CEA 10 -> D	11	0 -> CEA 10 -> D
G	10	0 -> CEA 11 -> F	10	0 -> CEA 11 -> F

1. During the first step an exchange between A and B, as well as C and F takes place. Both of these exchanges correspond to case 1 in 4.3. The randombit() function is assumed to return 0 on both occasions.
2. In step 2 E and D performs an exchange, along with C and G that also perform an exchange. The first of these correspond to case 1 and the second correspond to case 2 in figure fig:pgridexchange.
3. During step 3 D and A perform an exchange, which also is performed by B and C, along with F and E. The first of these correspond to case 3, where A directs D to B. When D performs an exchange with B their keys are extended with different bits, which is case 1. If we assume that the exchange between B and C happens a bit later, B will forward C to A since it is case 3. When C and A perform an exchange their keys will be extended due to case 1. The exchange between F and E causes F to issue an exchange with D. This exchange causes F to extend its key (case 2), since D has just extended its key in an exchange with B.
4. In step 4 G and F do an exchange, which is also performed by B and D. In the exchange between G and F their keys are extended since it is case 1. The exchange between B and D does not change anything since no forwarding in case 3 is possible. This is not unexpected since B and D were involved in an exchange in the previous step.
5. In the final step of the example E starts an exchange with B. This is also case 3 and E is forwarded to A. In the exchange between E and A, E extends its key due to case 2.

The exchange algorithm used to distribute responsibilities between two peers 34#34 and 35#35 is shown in figure fig:pgridexchange. It is quite complicated, but simulations have shown that it reaches a stable state in about the same time as the Freenet information sharing system, as presented in [ACMD$^+$02] and [AHP03]. See section sec:freenet or [FNP03] and [CMH$^+$02] for more details on Freenet.

The algorithm presented here assumes that 34#34 initiates the exchange. The algorithm presented here is a reworked version of the algorithm that closer matches the way it would be implemented (in most cases). For details on the original formulations of the algorithm see [Abe02], [Abe01], [APHS02] or [ACMD$^+$02]. All of these sources present slightly different versions of the algorithm, which makes it a little unclear exactly how the algorithm should be formulated.

Illustration 4.3: Pseudo-code for responsibility exchange in P-Grid

  exchange(p1, p2) {
      master = p1
      slave = p2
      // Make sure p2 has the longest key
      if (length(p1.key) > length(p2.key))
          swap(p1, p2)
      common = length(common_prefix(p1.key, p2.key))
      l1 = length(p1.key) - common
      l2 = length(p2.key) - common
      // Exchange references at common level
      if (common > 0)
          xchg_refs(p1, p2, common)
      if (l1 == 0 && l2 == 0)
          // Case 1: Extend both keys
          if (MYSELF == master)
              b = randombit()
              master.key += b
              sendbit(slave, 1 - b)
              REFS(common + 1) = {slave}
          else
              slave.key += recvbit(master)
              slave.refs(common + 1) = {master}
      else if (l1 == 0 && l2 > 0)
          // Case 2: Extend p1.key, which is shorter
          if (MYSELF == p1)
              p1.key += 1 - bit(p2.key, common + 1)
              REFS(common + 1) = {p2}
      else if (l1 > 0 && l2 > 0)
          // Case 3: Exchange data and tell p2 to do another exchange
          xchg_data(p1, p2)
          if (MYSELF == p1)
              p3 = recvpeer(p2)
              connect(p3)
              exchange(p1, p3)
          else
              sendpeer(p1, REFS(common + 1))
  }

The algorithm, as it is described in figure fig:pgridexchange, does not converge to a stable state rapidly enough. By adding a threshold on the minimum number of elements stored in order to extend the key by one bit and a threshold on the number of recursive calls allowed the algorithm reaches a stable state faster. For further performance related details see chapter 6.