הצגת המקור של הדף "קדמליה"

{{להשלים|כל הערך=כן|נושא=מחשוב}}
'''קדמליה''' (מ[[לועזית]]: '''Kademlia''', ובקיצור: '''Kad''') היא [[טבלת גיבוב]] מבוזרת (Distributed hash table, DHT) מדור שלישי, המשמשת ברשתות [[עמית לעמית|P2P]] שהומצאה על ידי פטר מיימאונקוב (Petar Maymounkov) ודייוויד מזיארס (David Mazières).{{הערה|1=[http://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf Kademlia: A Peer to peer information system Based on the XOR Metric]
}}

== פונקציית הגיבוב ופונקציית המרחק ==
בקדמליה ממופים כל הערכים המאוחסנים בעזרת פונקציית הגיבוב [[SHA-1]], הנותנת לכל ערך מפתח בן 160 [[בייט|בתים]]. פונקציית המרחק בין שני מפתחות היא פונקציית [[XOR]], כך נוצר מרחב חיפוש בו ניתן למקם את כל הערכים ולתאר את המרחקים ביניהם לפי מרחקי המפתחות. <br />בנוסף, ממופים כל הצמתים ברשת לפי אותן פונקציות גיבוב ומרחק ואותו מרחב בן 160 הבתים מכיל הן את הערכים והן את המשתתפים ברשת.

משך החיפוש בקדמליה יחסי ל-<math>log(n)</math>, כאשר n הוא מספר החברים ברשת.

== שימוש טיפוסי ==
השימוש הנפוץ ביותר ברשת הוא לצורך [[שיתוף קבצים]], בדוגמה הבאה מודגם חיפוש אחר קובץ ברשת:
# מחשב המחובר לרשת מעוניין למצוא קובץ בשם XXX.
# המחשב המחפש מפעיל את [[פונקציית גיבוב|פונקציית הגיבוב]] על השם XXX ומקבל YYY, ערך בן 128 ביט.
# המחפש מאתר בעזרת טבלת הניתוב (ראו בהמשך) את הדרך לעמית (Peer) האחראי על הערך YYY, בתהליך זה יש לכל היותר <math>log(n)</math> שלבים ברשת בת n עמיתים.
# המחשב האחראי על הערך YYY (זה שיש לו מזהה הקרוב ביותר ל-YYY) מדווח למחפש על רשימת המחשבים שדיווחו לו על כך שהם מכילים את הקובץ XXX.
# המחפש פונה אל כל איברי הרשימה ונרשם אצלם בתור להורדת הקובץ.

== טבלת ניתוב ==
הניתוב בקדמליה הוא הדרגתי, כל צומת (node) ברשת מעביר למחפש את הכתובת אל הצומת הבא. מפני שכל צומת מחזיק מידע מאוד מפורט על המתחם הקרוב אליו במרחב החיפוש ומידע דליל יותר על החלקים המרוחקים יותר, ה"קפיצות" אותן מבצע המחפש הן בצעדים שהולכים ומתקצרים (מבחינת המרחק בין ערכי פונקציית הגיבוב) וכך מובטח החיפוש בן <math>log(n)</math> שלבים לכל היותר.

== מימושים עיקריים ==
את הפרוטוקול מממשת התוכנה הפופולרית [[eMule]], שהיא המחליפה של [[eDonkey2000 (תוכנה)|eDonkey]] ותוכנות P2P נוספות משתמשות בו.

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}

== הערות שוליים ==
{{הערות שוליים}}

[[קטגוריה:שיתוף קבצים]]