Lo de ver el problema de Generales Bizantinos en cualquier cosa es como Nico viendo blockchains por doquier.
Es evidente que tus conocimientos de informática son escasos. Aunque reconozco que, incluso para los del gremio, las redes tipo Kadmelia son complejas.
De todas maneras ya te puse, hace no mucho, el link de las pruebas matemáticas que aseguran la entrega de mensajes en la red Kadmelia de Safe. Se ve que no has hecho tus deberes. Propiedad Nº3.
Appendix:
Proofs
We prove that whenever the invariant holds, the desired properties are guaranteed.
Let bd(x, y) be the bucket distance between two addresses x and y, x ^ y the XOR distance, and bi(x, y) = 512 - bd(x, y) the bucket index. Equivalently, the bi(x, y)-th bit is the first (most significant) one where x and y disagree.
Lemma 1
y is XOR-closer to x than z if and only if y agrees with x in the most significant bit where y disagrees with z. That is, the ***owing are equivalent:
x ^ y < x ^ z
x and y agree in the bi(y, z)-th bit.
x and z disagree in the bi(y, z)-th bit.
Proof: x ^ y < x ^ z means that in the most significant bit where x ^ y and x ^ z disagree, x ^ y has a 0. But x ^ y and x ^ z disagree in the same bits as y and z, i. e. they first disagree in the bi(y, z)-th bit. Since x ^ y has a 0 there, that means that x and y agree there. Similarly, since x ^ z is 1 in that place, x and z disagree there.
Lemma 2
If n is in the close group to d, it has every node m in its routing table which is even closer to d.
Proof: By Lemma 1, m is closer to d if and only if d and n agree in the bi(m, n)-th digit, i. e. if m would belong in a bucket i of n such that d ^ n has a 0 in the i-th position. In other words, the nodes closer to d than n are exactly those which belong in such a bucket. If there were GROUP_SIZE of them, n wouldn't be close to d, so there are less than GROUP_SIZE of them, which means none of these buckets is full. Therefore m is actually in one of those buckets of n because of the invariant.
Property 1
If a node is among the GROUP_SIZE closest nodes in the network, it cannot have GROUP_SIZE other, closer nodes in its routing table. Therefore is_close returns true.
For the converse, assume there are GROUP_SIZE nodes that are closer to the target t than our node's address n. That such a node c is closer to t means t ^ c < t ^ n, which by Lemma 1 is equivalent to c belonging in the i-th bucket of n for some i such that n and t disagree in the i-th bit. Since by the invariant each such bucket contains either all nodes with that bucket distance or GROUP_SIZE such nodes, the routing table then has at least GROUP_SIZE such entries c.
Property 2
Let n and m be in the close group of d. Witout loss of generality assume that n is closer to d. Then by Lemma 2, m has n in its routing table. Therefore, the two are connected.
Property 3
Thanks to property 2, we only have to show that the message reaches the node closest to the destination d, as from there it will directly be sent to all the other close nodes.
For that, we show that every node n that is not closest to d increases the number of good leading bits in the next hop:
A bit i is good for n if either n ^ x is 0 in that bit, or n's i-th bucket is empty.
Let the current node n not be closest to the destination d, and assume that the first i bits are good. The message is sent to the entry m in n's routing table which is closest to d, so we need to prove that m has at least i + 1 good leading bits.
Since m minimizes the distance to d among the table entries, it must be in the first nonempty bucket k of n such that n and d disagree in the k-th bit. Thus the k-th is the first bit that is not good for n, that is, k = i + 1. Since m and d agree there, it is, however, good for m.
If we can show that the first i bits are also still good for m, then it ***ows that m has in fact at least i + 1 good leading bits:
But m and n agree in the first i bits. So wherever n ^ x has a 0, m ^ x also does. Also, the nodes with bucket distance j for every j <= i are the same, so whenever n's j-th bucket is empty, the invariant implies that there are no nodes with that bucket distance in the network and therefore m's j-th bucket must also be empty.
Property 4
This ***ows immediately from Property 3, since only PARALLELISM different messages are created by the sender.
Property 5
There are 512 bucket addresses, and each of them has only GROUP_SIZE close nodes.
Proofs
We prove that whenever the invariant holds, the desired properties are guaranteed.
Let bd(x, y) be the bucket distance between two addresses x and y, x ^ y the XOR distance, and bi(x, y) = 512 - bd(x, y) the bucket index. Equivalently, the bi(x, y)-th bit is the first (most significant) one where x and y disagree.
Lemma 1
y is XOR-closer to x than z if and only if y agrees with x in the most significant bit where y disagrees with z. That is, the ***owing are equivalent:
x ^ y < x ^ z
x and y agree in the bi(y, z)-th bit.
x and z disagree in the bi(y, z)-th bit.
Proof: x ^ y < x ^ z means that in the most significant bit where x ^ y and x ^ z disagree, x ^ y has a 0. But x ^ y and x ^ z disagree in the same bits as y and z, i. e. they first disagree in the bi(y, z)-th bit. Since x ^ y has a 0 there, that means that x and y agree there. Similarly, since x ^ z is 1 in that place, x and z disagree there.
Lemma 2
If n is in the close group to d, it has every node m in its routing table which is even closer to d.
Proof: By Lemma 1, m is closer to d if and only if d and n agree in the bi(m, n)-th digit, i. e. if m would belong in a bucket i of n such that d ^ n has a 0 in the i-th position. In other words, the nodes closer to d than n are exactly those which belong in such a bucket. If there were GROUP_SIZE of them, n wouldn't be close to d, so there are less than GROUP_SIZE of them, which means none of these buckets is full. Therefore m is actually in one of those buckets of n because of the invariant.
Property 1
If a node is among the GROUP_SIZE closest nodes in the network, it cannot have GROUP_SIZE other, closer nodes in its routing table. Therefore is_close returns true.
For the converse, assume there are GROUP_SIZE nodes that are closer to the target t than our node's address n. That such a node c is closer to t means t ^ c < t ^ n, which by Lemma 1 is equivalent to c belonging in the i-th bucket of n for some i such that n and t disagree in the i-th bit. Since by the invariant each such bucket contains either all nodes with that bucket distance or GROUP_SIZE such nodes, the routing table then has at least GROUP_SIZE such entries c.
Property 2
Let n and m be in the close group of d. Witout loss of generality assume that n is closer to d. Then by Lemma 2, m has n in its routing table. Therefore, the two are connected.
Property 3
Thanks to property 2, we only have to show that the message reaches the node closest to the destination d, as from there it will directly be sent to all the other close nodes.
For that, we show that every node n that is not closest to d increases the number of good leading bits in the next hop:
A bit i is good for n if either n ^ x is 0 in that bit, or n's i-th bucket is empty.
Let the current node n not be closest to the destination d, and assume that the first i bits are good. The message is sent to the entry m in n's routing table which is closest to d, so we need to prove that m has at least i + 1 good leading bits.
Since m minimizes the distance to d among the table entries, it must be in the first nonempty bucket k of n such that n and d disagree in the k-th bit. Thus the k-th is the first bit that is not good for n, that is, k = i + 1. Since m and d agree there, it is, however, good for m.
If we can show that the first i bits are also still good for m, then it ***ows that m has in fact at least i + 1 good leading bits:
But m and n agree in the first i bits. So wherever n ^ x has a 0, m ^ x also does. Also, the nodes with bucket distance j for every j <= i are the same, so whenever n's j-th bucket is empty, the invariant implies that there are no nodes with that bucket distance in the network and therefore m's j-th bucket must also be empty.
Property 4
This ***ows immediately from Property 3, since only PARALLELISM different messages are created by the sender.
Property 5
There are 512 bucket addresses, and each of them has only GROUP_SIZE close nodes.
)
