KADEMLIA

Proposto por Petar Maymounkov e David Mazèries, Sistema de armazenamento e busca P2P. Totalmente descentralizado

A Rede

Para ingressar na rede, é necessário conhecer o IP de um nó participante.
Cada nó recebe um ID calculado através da aplicação de uma função de hash no seu IP.
Cada arquivo recebe uma Chave, obtida através da função de hash.
Os IDs e chaves possuem 160 bits.
Os pares identificam a localização do arquivo. Os pares são distribuídos aos nós, de acordo com a proximidade com os seus Ids. A distância entre dois identificadores (chaves ou IDs) é calculada com o XOR interpretado como um inteiro.

K-Listas

Cada nó mantém listas de contatos de outros nós. O nó mais recente fica na cauda da lista. A cada mensagem trocada as listas são atualizadas

Protocolo

É formado por 4 RPC’s (Remote Procedure Calls); find_node, find_value, store, ping. A busca é recursiva

Busca

Ex: Um nó deseja encontrar uma chave y.
● Ele busca em suas k-listas os IDs mais próximos desta chave.
● Ele envia então o pedido aos nós. Se algum deles possui o arquivo a busca acaba.
● Se não, os nós enviam o pedido aos nós de ID mais próximo de suas k-listas.

http://www.cic.unb.br/~bordim/TD/Arquivos/G02_Slides.pdf

Marcele Barreto Soares

mat: 104040495