ในเครือข่ายแบบเพียร์ทูเพียร์Koordeเป็น ระบบ ตารางแฮชแบบกระจาย (DHT) ที่อิงตามChord DHTและกราฟ De Bruijn ( ลำดับ De Bruijn ) ด้วยความเรียบง่ายของ Chord ทำให้ Koorde มีจำนวน ฮอป O (log n )ต่อโหนด (โดยที่nคือจำนวนโหนดใน DHT) และจำนวนฮ${\displaystyle O\left({\frac {\log n}{\log(\log n)}}\right)}$อปต่อคำขอค้นหา โดยมี เพื่อนบ้าน O (log n )ต่อโหนด

แนวคิด Chord นั้นอิงอยู่กับ ตัวระบุที่หลากหลาย(เช่น 2 ¹⁶⁰ ) ในโครงสร้างแบบวงแหวนโดยที่ตัวระบุสามารถแทนได้ทั้งโหนดและข้อมูล โหนดผู้สืบทอดมีหน้าที่รับผิดชอบช่วงของรหัสทั้งหมดระหว่างตัวมันเองกับโหนดก่อนหน้า

Koorde มีพื้นฐานมาจาก Chord และกราฟ De Bruijn ( ลำดับ De Bruijn ) ใน กราฟ De Bruijn มิติ dจะมีโหนด2d ^โหนด โดยแต่ละโหนดจะมี ID ที่ไม่ซ้ำกันซึ่งประกอบด้วย d บิตโหนดที่มี ID iจะเชื่อมต่อกับโหนด2i mod 2dและ²ⁱ + 1 mod ^2dด้วยคุณสมบัตินี้อัลกอริทึมการกำหนดเส้นทางสามารถกำหนดเส้นทางไปยังปลายทางใดก็ได้ในd ฮ อปโดยการ "เลื่อน" บิตของ ID ปลายทางเข้าไปทีละน้อย แต่เฉพาะในกรณีที่มิติของระยะทางระหว่าง mod 1d และ 3d เท่ากันเท่านั้น

การส่งข้อความจากโหนดmไปยังโหนดkทำได้โดยการนำตัวเลขmมาเลื่อนบิตของkทีละบิตจนกว่าตัวเลข m จะถูกแทนที่ด้วยkการเลื่อนแต่ละครั้งจะสอดคล้องกับการกระโดดไปยังที่อยู่ระดับกลางถัดไป การกระโดดนี้ถูกต้องเนื่องจากเพื่อนบ้านของแต่ละโหนดคือผลลัพธ์ที่เป็นไปได้สองอย่างของการเลื่อน 0 หรือ 1 ไปยังที่อยู่ของตัวเอง เนื่องจากโครงสร้างของกราฟเดอ บรูอิน เมื่อบิตสุดท้ายของkถูกเลื่อนแล้ว คำถามจะอยู่ที่โหนดkโหนดkจะตอบว่าคีย์kมีอยู่ หรือไม่

ตัวอย่างเช่น เมื่อต้องการส่งข้อความจากโหนด 2 (ซึ่งคือ010) ไปยังโหนด 6 (ซึ่งคือ110) ขั้นตอนจะเป็นดังนี้:

1. โหนด 2 ส่งต่อข้อความไปยังโหนด 5 (โดยใช้การเชื่อมต่อกับ2 i + 1 mod 8 ) เลื่อนบิตไปทางซ้าย และใส่1บิตที่อายุน้อยที่สุด (ด้านขวา)
2. โหนด 5 ส่งต่อข้อความไปยังโหนด 3 (โดยใช้การเชื่อมต่อกับ2 i + 1 mod 8 ) เลื่อนบิตไปทางซ้าย และวางไว้1เป็นบิตที่อายุน้อยที่สุด (ด้านขวา)
3. โหนด 3 ส่งต่อข้อความไปยังโหนด 6 (โดยใช้การเชื่อมต่อกับ2 i mod 8 ) เลื่อนบิตไปทางซ้าย และใส่0บิตที่ใหม่ที่สุด (ด้านขวา) เป็นบิตที่ใหม่ที่สุด

การ กำหนดเส้นทางแบบ de Bruijn มิติ dสามารถขยายไปสู่ฐานk ได้โดยที่โหนดiจะเชื่อมต่อกับโหนดk • i + j mod kdโดยที่ 0 ≤ j < kเส้นผ่านศูนย์กลางจะลดลงเหลือΘ (log _k n )โหนด Koorde iจะเก็บตัวชี้ไปยัง โหนดต่อเนื่อง kโหนด โดยเริ่มจากโหนดก่อนหน้าของk • i mod kdแต่ละขั้นตอนการกำหนดเส้นทางแบบ de Bruijn สามารถจำลองได้ด้วยจำนวนข้อความที่คาดหวังคงที่ ดังนั้นการกำหนดเส้นทางจึงใช้ จำนวนฮอปที่คาดหวัง O (log _k n )สำหรับk = Θ(log n )เราจะได้ดีกรี และเส้นผ่านศูนย์กลางΘ (log n )${\displaystyle \Theta \left({\frac {\log n}{\log(\log n)}}\right)}$

ฟังก์ชันn.lookup ( k , shift , i ) { ถ้าk ∈ ( n , s ] ให้คืนค่า( s ) มิฉะนั้นถ้าi ∈ ( n , s ] ให้คืนค่าp.lookup ( k , shift << 1 , i ∘ topBit ( shift ) ) ; มิฉะนั้นให้คืนค่าs.lookup ( k , shift , i ) }

รหัสเทียมสำหรับอัลกอริทึมการค้นหา Koorde ที่โหนดn:

• kเป็นกุญแจสำคัญ
• Iคือโหนด De Bruijn ในจินตนาการ
• pคือการอ้างอิงถึงรุ่นก่อนหน้าของ2n
• sคือการอ้างอิงถึงผู้สืบทอดของn