Kademlia

Maymounkov et al, 2002

Papers We Love Taipei (June 2020)

Introduction

  • Motivation
  • How Kademlia works
  • Kademlia in practice

Distributed Hash Table

Motivation

  • Motivated by p2p problems in the wild
  • Lack of single point of failure
  • Resistant to node failure and quick lookups

How does Kademlia work?

  • Kademlia Binary Tree
  • XOR Metric
  • Node state
  • Kademlia protocol

Kademlia Binary Tree

Node state

Kademlia protocol

  • PING
  • STORE
  • FIND_NODE
  • FIND_VALUE

How does node lookup work?

  • Locate k closest peers of some NodeID
  • Recursive lookup
  • Fundamental building block

Kademlia in practice

  • Bittorrent
  • IPFS
  • Ethereum

Summary

  • Recap: what; why; how; applications
  • Elegant and practical, not perfect
  • Staple in p2p protocol design

Thanks!

Select a repo