Nowadays Kademlia is one of the most widely used DHTs (Distributed Hash Table) in P2P (peer-to-peer) networks. This work studies one essential question about Kademlia overlay networks from a mathematical perspective: how long does it take to locate a node? To answer it, we introduce a random graph K to model a Kademlia overlay and study how long it takes to locate a given vertex in K by using Kademlia's routing algorithm. / Aujourd'hui Kademlia est l'un des les plus utilisés DHTs (Distributed Hash Tableau) dans les réseaux P2P (peer-to-peer). Cet article étudie une question essentielle des réseaux "overlay" de Kademlia d'un point de vue mathématique: combien de temps faut-il pour localiser un noeud? Pour y répondre, nous introduisons un graphe aléatoire K pour modéliser un réseau de Kademlia et étudier la complexité d'un algorithme de routage de Kademlia.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.114333 |
| Date | January 2013 |
| Creators | Cai, Xing Shi |
| Contributors | Luc P Devroye (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0022 seconds