نمایش مبدأ برای کادملیا


کادملیا (<span lang="en">'''Kademlia'''</span> ) یک [[جدول درهم‌سازی توزیع‌شده|جدول هشی توزیع شده]] برای [[شبکه رایانه‌ای|شبکه های کامپیوتری]] [[تمرکززدایی|نامتمرکز]] [[همتا به همتا]] است که توسط پتار میمونونکوف و دیوید مازییرز در سال 2002 طراحی شده است. <ref name="kademlia-paper">[http://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf Kademlia: A Peer-to-peer information system based on the XOR Metric]</ref> <ref>{{Cite web|url=http://www.scs.stanford.edu/~dm/home/papers/|title=Papers by David Mazières|website=www.scs.stanford.edu}}</ref> ساختار شبکه و تبادل اطلاعات را از طریق جستجوی [[گره (شبکه)|گره]] مشخص می کند. گره های کادملیا با استفاده از [[قرارداد داده‌نگار کاربر|UDP]] میان یکدیگر ارتباط برقرار می کنند. یک [[شبکه]] [[مجازی]] یا [[شبکه‌های همپوشان|همپوشان]] توسط گره های شرکت کننده تشکیل می شود. هر گره توسط یک شماره یا ''شناسه گره'' مشخص می ''شود'' . شناسه گره نه تنها به عنوان شناسایی عمل می کند بلکه الگوریتم کادملیا از ''شناسه گره'' برای یافتن مقادیر (معمولاً [[تابع هش|هش]] فایل یا کلمات کلیدی) استفاده می کند. در واقع ، ''شناسه گره'' نقشه مستقیمی را برای تهیه هش ها فراهم می کند و این گره اطلاعات مربوط به محل دسترسی به فایل یا منبع را ذخیره می کند. 

الگوریتم هنگام جستجو برای برخی از مقادیر ، باید کلید همراه را بشناسد و در چندین گام شبکه را کاوش کند. هر گام گره هایی را که به کلید نزدیک تر هستند پیدا می کند تا زمانی که گره تماس گرفته شده مقدار را برگرداند یا گره های نزدیک تری پیدا نکنند. این روش بسیار کارآمد است: مانند بسیاری دیگر از {{H:title|جدول هش توزیع شده|جداول هش توزیع شده (DHT)}} ، کادملیا فقط با [[نماد O بزرگ|<math>O(\log (n))</math>]] گره در طول جستجو از کل <math>n</math> گره های موجود در سیستم سر و کار خواهد داشت. 

مزایای بیشتر این روش به ویژه در ساختار غیر متمرکز یافت می شود ، جایی که باعث افزایش مقاومت در برابر [[حمله محروم‌سازی از سرویس|حملات امتناع از سرویس دهی   می شود]] . حتی اگر مجموعه ای از گره ها سرریز شود ، این امر تأثیر محدودی بر در دسترس بودن شبکه خواهد داشت ، زیرا شبکه با گره زدن شبکه به اطراف این "سوراخ ها" ، خود را بازیابی می کند. 

پیاده سازی [[پروژه اینترنت مخفی|اینترنت مخفی]] کادملیا برای کاهش آسیب پذیری های کادملیا در برابر حملات مانند [[حمله سیبیل|حملات سیبیل]] اصلاح شده است. <ref name="urlThe Network Database - I2P">{{Cite web|url=https://geti2p.net/en/docs/how/network-database#threat|title=The Network Database - I2P|format=|website=|accessdate=}}</ref> 

== جزئیات سیستم ==
اولین شبکه های همتا به همتای به اشتراک گذاری فایل ها ، مانند [[نپستر]] [[نپستر|Napster]] ، برای ایجاد هماهنگ سازی مراجعات در شبکه به یک پایگاه داده مرکزی متکی بودند. شبکه های همتا به همتای نسل دوم ، مانند [[ناتلا]]  [[ناتلا|Gnutella]] ، برای یافتن پرونده ها از [[جریان سیل آسا|فلودینگ]] استفاده می کردند و هر گره را در شبکه جستجو می کردند. شبکه های همتا به همتا نسل سوم از [[جدول درهم‌سازی توزیع‌شده|جداول هش توزیع شده]] برای جستجوی فایل ها در شبکه استفاده می کنند. ''جداول هش توزیع'' شده ، مکان منابع در سراسر شبکه را ذخیره می کنند. معیار اصلی این پروتکل ها مکان یابی سریع گره های مورد نظر است. 

کادملیا از یک روش محاسبه "فاصله" بین دو گره استفاده می کند. این فاصله به صورت [[یای انحصاری]] بین دو شناسه گره محاسبه می شود و نتیجه را به عنوان یک [[عدد صحیح]] بی علامت برمی گرداند. کلیدها و شناسه های Keys و Node از یک قالب و طول یکسان برخوردار هستند ، بنابراین می توان فاصله را بین آنها به طور یکسان محاسبه کرد. شناسه گره معمولاً یک عدد تصادفی بزرگ است که با هدف منحصر به فرد بودن برای یک گره خاص انتخاب می شود (به [[شناسه منحصربه‌فرد جهانی|UUID]] مراجعه کنید).گاه اتفاق می افتد که گره هایی که از نظرجغرافیایی به طور گسترده ای  - بطورمثال  آلمان و استرالیا - از هم دور و جدا هستند ، اگر شناسه های گره تصادفی مشابهی را انتخاب نموده باشند ،می توانند  "همسایه" قلمداد شوند. 

یای انحصاری به این دلیل انتخاب شده است زیرا به عنوان یک [[متریک (ریاضیات)|تابع فاصله]] بین تمام شناسه های گره عمل می کند. به طور مشخص: 

* فاصله بین یک گره و خودش صفر است 
* متقارن است: "مسافت" که از A تا B و B از A محاسبه می شود ، یکسان هستند 
* از [[نابرابری مثلثی]] تبعیت می کند:  با فرض این که A ، B و C [[رأس (هندسه)|راس]] (نقاط) یک مثلث هستند ، پس فاصله A تا B کوتاهتر از (یا مساوی با) جمع فاصله از A تا C به علاوه فاصله از C به B  است. 

این سه شرط کافی است تا اطمینان حاصل شود که یای انحصاری  همه ویژگیهای مهم و اصلی یک تابع فاصله "واقعی" را دارد، در عین حال ارزان و ساده برای محاسبه است. <ref name="kademlia-paper"/> 

هر تکرار جستجوی کادملیا کمی به هدف نزدیکتر می شود. یک شبکه '''اساسی''' کادملیا با 2<sup>n</sup>  گره برای پیدا کردن گره مقصد تنها به ''n'' تکرار(در بدترین حالت) نباز خواهد داشت . 

=== جداول مسیریابی با اندازه ثابت ===
<small>''این بخش برای استفاده از تنها یک بیت ساده سازی شده است. برای اطلاعات بیشتر در مورد جداول مسیریابی واقعی به بخش جداول مرجع تقویت شده مراجعه کنید.''</small> 

جداول مسیریابی اندازه ثابت در نسخه [http://www.scs.stanford.edu/~dm/home/papers/kpos.pdf قبل از رسیدگی] مقاله اصلی ارائه شده است و در نسخه بعدی فقط برای برخی از اثبات های ریاضی استفاده می شود. یک اجرای واقعی کادملیا دارای جدول مسیریابی با اندازه ثابت نیست بلکه دارای جدول مسیریابی با اندازه پویا است. 

جداول مسیریابی کادملیا شامل یک ''لیست'' برای هر بیت شناسه گره است. (به عنوان مثال اگر یک شناسه گره شامل 128 بیت باشد ، یک گره تعداد 128 ''عدد از این'' ''لیستها'' را نگه می دارد. ) یک لیست دارای ورودی های زیادی است. هر ورودی در یک ''لیست'' داده های لازم را برای یافتن گره دیگر در اختیار دارد. داده های موجود در هر ورودی ''لیست'' معمولاً ''[[آدرس IP]]'' ، ''پورت'' و ''شناسه'' گره دیگر است. هر ''لیست'' با فاصله مشخصی از گره مطابقت دارد. گره های که می تواند در n <sup>امین</sup> ''لیست'' جا بگیرند باید یک بیت n <sup>ام</sup> متفاوت از شناسه (ID) گره داشته باشند. اولین بیت n-1 شناسه نامزد باید با شناسه گره مطابقت داشته باشد. این بدان معنی است که جمع کردن ''لیست'' اول بسیار آسان است زیرا 1/2 گره های موجود در شبکه کاندیدای قرارگرفتن در  دوردست هستند. در ''لیست'' بعدی فقط می توان از 1/4 از گره های موجود در شبکه استفاده کرد (یک بیت نزدیک تر از اول) و غیره. 

با داشتن یک شناسه 128 بیتی ، هر گره در شبکه گره های دیگر را در یکی از 128 فاصله مختلف ، یک فاصله خاص در هر بیت طبقه بندی می کند. 

وقتی گره ها در شبکه برخورد داشته باشند ، به لیست ها اضافه می ''شوند'' . این کار شامل عملیات ذخیره سازی و بازیابی و حتی کمک به گره های دیگر برای یافتن کلید است. هر گره ای که با آن روبرو می شوید برای درج در لیست ها در نظر گرفته می شود. بنابراین ، دانشی که گره از شبکه دارد بسیار پویا است. این ویژگی باعث می شود شبکه به طور مداوم به روز شود و مقاومت در برابر خرابی ها یا حملات را افزایش دهد. 

در ادبیات کادملیا، از ''لیست'' ها به ''(k-سطل) یاد می شود'' . ''k'' یک عدد سیستمی مانند 20 است. هر ''(k-سطل)''  ''لیستی است'' که دارای ورودی های ''K'' در داخل خودش است. یعنی برای شبکه ای با k = 20 ، هر گره دارای ''لیست'' هایی است که حداکثر 20 گره را برای یک بیت خاص (فاصله خاص از خود) دارد. 

از آنجا که گره های ممکن برای هر''(k-سطل)''به سرعت کاهش می یابد (زیرا گره های بسیار کمی در آن نزدیکی وجود خواهد داشت) ،  بیت پایینتر ''(k-سطل)'' ، تمام گره ها را در آن بخش از شبکه به طور کامل نگاشت می کنند. از آنجا که مقدار شناسه های ممکن بسیار بزرگتر از هر تعداد گره ممکن است  ، برخی از ''(k-سطل) ها'' که مربوط به مسافت های بسیار کوتاه هستند ، خالی باقی می مانند. 
[[پرونده:Dht_example_SVG.svg|بندانگشتی|420x420پیکسل| پارتیشن شبکه برای گره '''110''' ]]
شبکه ساده سمت راست را در نظر بگیرید. اندازه شبکه 2 به توان 3 یا 8 کلید و گره حداکثر است. هفت گره برای شرکت کردن وجود دارند. حلقه های کوچک در پایین گره مورد نظر گره شش (دودویی 110) به رنگ سیاه است. در این شبکه سه ''سطل K'' برای هر گره وجود دارد. گره های صفر ، یک و دو (باینری 000 ، 001 و 010) نامزد دورترین ''سطل K هستند'' . گره سه (دودویی 011 ، نشان داده نشده است) در شبکه شرکت نمی کند. در ''سطل k'' میانی ، گره های چهار و پنج (باینری 100 و 101) قرار می گیرند. سرانجام ، ''سطل'' سوم ''k'' فقط می تواند شامل گره هفت باشد (باینری 111). هر یک از سه ''سطل K'' در یک دایره خاکستری محصور شده است. اگر اندازه ''k-bucket'' دو بود ، دورترین ''2-سطل'' فقط می تواند حاوی دو تا از سه گره باشد. به عنوان مثال ، اگر گره شش گره یک و دو را در دورترین 2 سطل داشته باشد ، برای یافتن محل (آدرس ip) گره صفر ، باید یک جستجوی شناسه گره به این گره ها بخواهید. هر گره همسایگی خود را به خوبی ''می شناسد'' و با چند گره دورتر ارتباط دارد که می تواند به گره های دیگر دورتر کمک کند. 

مشخص است که گره هایی که مدت طولانی در یک شبکه متصل شده اند ، احتمالاً در آینده برای مدت طولانی متصل خواهند بود. <ref>Stefan Saroiu, P. Krishna Gummadi and Steven
D. Gribble. A Measurement Study of Peer-to-Peer File Sharing Systems. Technical Report UW-CSE-01-06-02, University of Washington, Department of Computer Science and Engineering, July 2001.</ref> <ref>Daniel Stutzbach and Reza Rejaie. [http://www.barsoom.org/papers/imc-2006-churn.pdf Understanding Churn in Peer-to-Peer Networks] Section 5.5 Uptime Predictability, Internet Measurement Conference, Rio de Janeiro, October, 2006.</ref> به دلیل این توزیع آماری ، کادملیاگره های متصل طولانی را برای ماندن در سطل های K انتخاب می کند. این تعداد گره های معتبر شناخته شده را در آینده افزایش می دهد و شبکه پایدار تری را فراهم می کند. 

هنگامی که یک ''سطل k'' کامل است و یک گره جدید برای آن ''سطل k'' کشف می شود ، کمترین گره اخیراً در ''سطل k'' دیده می شود PINGed. اگر مشخص شود که گره هنوز زنده است ، گره جدید در یک لیست ثانویه ، یک حافظه نهان جایگزین قرار می گیرد. حافظه پنهان جایگزینی فقط درصورتی استفاده می شود که یک گره در ''سطل k'' جواب ندهد. به عبارت دیگر: گره های جدید فقط در صورت ناپدید شدن گره های قدیمی استفاده می شوند. 

=== پیام های پروتکل ===
کادملیاچهار پیام دارد. 

* PING - برای تأیید اینکه گره هنوز زنده است استفاده می شود. 
* STORE - یک جفت (کلید ، ارزش) را در یک گره ذخیره می کند. 
* FIND_NODE - گیرنده درخواست گره های k را در سطل خود که نزدیکترین آنها به کلید درخواست شده است ، بازمی گرداند. 
* FIND_VALUE - مشابه FIND_NODE ، اما اگر گیرنده درخواست کلید درخواستی را در فروشگاه خود داشته باشد ، مقدار مربوطه را برمی گرداند. 

هر پیام RPC شامل یک مقدار تصادفی از آغازگر است. این تضمین می کند که هنگام دریافت پاسخ ، با درخواست قبلی ارسال شده مطابقت دارد. (به کوکی جادویی مراجعه کنید) 

=== گره ها را پیدا کنید ===
جستجوی گره ها می توانند به صورت غیر همزمان انجام شوند. مقدار جستجوی همزمان توسط α مشخص شده و به طور معمول سه است. یک گره با جستجوی گره های α در ''سطل های K'' که نزدیکترین آن به کلید مورد نظر است ، یک درخواست FIND_NODE را آغاز می کند. هنگامی که این گره های گیرنده درخواست را دریافت می کنند ، در ''سطل های K'' آنها نگاه می کنند و نزدیکترین گره های ''k را'' به کلید مورد نظر خود باز می گردانند. درخواست کننده با نتایج (شناسه گره) که دریافت می کند ، لیست نتایج را به روز می کند و بهترین ''k'' ((گره های k که به کلید جستجو نزدیکتر هستند) را نگه می دارد و به سؤالات پاسخ می دهد. سپس درخواست از این ''K'' بهترین نتایج را انتخاب کنید و صدور درخواست به آنها، و دوباره و دوباره تکرار این فرایند است. از آنجا که هر گره نسبت به سایر گره ها شناخت بهتری نسبت به محیط اطراف خود دارد ، نتایج دریافت شده گره های دیگری خواهد بود که هر بار به کلید جستجو نزدیکتر و نزدیک تر می شوند. این تکرارها تا زمان بازگشت هیچ گره ای که به بهترین نتایج قبلی نزدیک باشد ، ادامه می یابد. هنگامی که تکرارها متوقف می شوند ، بهترین گره k در لیست نتایج آنهایی هستند که در کل شبکه نزدیک به کلید مورد نظر هستند. 

اطلاعات گره را می توان با [[زمان تأخیر چرخشی|زمان سفر دور]] یا RTT اضافه کرد. از این اطلاعات برای انتخاب یک زمان اختصاصی برای هر گره مشاوره استفاده می شود. هنگامی که یک پرس و جو پایان یافت ، می توان پرس و جو دیگری را آغاز کرد ، هرگز از درخواستهای α در همان زمان تجاوز نکنید. 

=== یافتن منابع ===
اطلاعات با نقشه برداری از آن در یک کلید قرار دارند. یک [[تابع هش|هش]] معمولاً برای نقشه استفاده می شود. به دلیل پیام STORE قبلی ، گره های فروشگاه دارای اطلاعات خواهند بود. پیدا کردن یک مقدار از همان روشی که مکانهای نزدیک به یک کلید را پیدا می کنید پیروی می کند ، به جز جستجو وقتی که یک گره مقدار درخواستی را در فروشگاه خود داشته باشد خاتمه می یابد و این مقدار را برمی گرداند. 

مقادیر در چندین گره (k از آنها) ذخیره می شوند تا گره ها بتوانند بیایند و بروند و همچنان مقداری از گره را در دسترس داشته باشند. بطور دوره ای ، گره ای که مقدار را ذخیره می کند ، شبکه را کاوش می کند تا گره های k را که به مقدار کلیدی نزدیک هستند پیدا کنند و مقدار آن را بر روی آنها تکرار کنند. این گره ها را ناپدید می کند. 

همچنین ، برای مقادیر محبوب که ممکن است درخواست های زیادی داشته باشند ، با داشتن یک گیرنده این مقدار را در بعضی از گره های نزدیک ، اما خارج از آن ، نزدیکترین k ، بار در گره های فروشگاه کم می شود. به این ذخیره سازی جدید حافظه پنهان گفته می شود. در این روش بسته به مقدار درخواست ، مقدار دورتر و دورتر از کلید ذخیره می شود. این امر به جستجوهای رایج اجازه می دهد سریعتر یک فروشگاه را پیدا کنند. از آنجا که مقدار از گره ها دورتر از کلید بازگردانده می شود ، این "نقاط داغ" احتمالی را کاهش می دهد. ذخیره گره ها بسته به فاصله آنها از کلید ، مقدار را پس از مدت مشخص کاهش می دهد. 

برخی از پیاده سازی ها (به عنوان مثال کد ) نه همانند سازی و نه حافظه پنهانی دارد. هدف از این کار حذف اطلاعات قدیمی به سرعت از سیستم است. گره ای که پرونده را تهیه می کند ، به صورت دوره ای اطلاعات را روی شبکه تازه می کند (پیام های FIND_NODE و STORE را انجام دهید). وقتی همه گره های موجود در فایل آفلاین شوند ، هیچ کس مقادیر (منابع و کلمات کلیدی) آن را تازه نمی کند و اطلاعات در نهایت از شبکه ناپدید می شوند. 

=== پیوستن به شبکه ===
گره ای که مایل به پیوستن به شبکه است ابتدا باید از یک فرآیند راه انداز شروع شود. در این مرحله ، گره اتصال می بایست [[نشانی آی‌پی|آدرس IP]] و پورت یک گره دیگر - یک گره راه انداز (از کاربر یا از یک لیست ذخیره شده) را بشناسد - این هم اکنون در شبکه کادملیاشرکت می کند. اگر گره پیوستن هنوز در شبکه شرکت نکرده باشد ، یک شماره شناسه [[اعداد تصادفی|تصادفی]] را محاسبه می کند که تصور می شود قبلاً به هیچ گره دیگری اختصاص نیافته است. تا زمان خروج از شبکه از این ID استفاده می کند. 

گره اتصال دهنده گره راه انداز را در یکی از ''سطل های K'' آن قرار می دهد. گره اتصال سپس یک گره را از شناسه خود در برابر گره راه انداز انجام می دهد (تنها گره دیگری که می داند). "خود جستجو" ''سطل'' های دیگر ''K را'' با شناسه گره جدید جمع می کند ، و سطل های K- گره اتصال را با گره هایی در مسیر بین آن و گره راه انداز جمع می کند. پس از این ، گره پیوستگی تمام ''سطل های K را'' دورتر از k-bucket می کند که گره راه انداز در آن قرار می گیرد. این تازه سازی فقط جستجوی یک کلید تصادفی است که در آن محدوده ''k-bucket'' قرار دارد. 

در ابتدا گره ها یک ''سطل K دارند'' . هنگامی که ''سطل k'' کامل می شود ، می توان آنرا تقسیم کرد. شکاف در صورتی رخ می دهد که دامنه گره ها در ''سطل k ،'' شناسه مخصوص خود گره را بپیماید (مقادیر در سمت چپ و راست در یک درخت باینری). کادملیاحتی این قاعده را برای یک "نزدیکترین گره" ''k-سطل'' آرام می کند ، زیرا به طور معمول یک سطل منفرد با فاصله ای مطابقت می کند که تمام گره هایی که به این گره نزدیکترین هستند وجود داشته باشد ، ممکن است آنها بیش از k باشند ، و ما آن را می خواهیم. همه آنها را بشناسیم ممکن است معلوم شود که یک درخت باینری بسیار نامتعادل در نزدیکی گره وجود دارد. اگر ''k'' 20 باشد ، و 21 گره با پیشوند "xxx0011 ....." وجود دارد و گره جدید "xxx0000 ''11001'' " است ، گره جدید می تواند شامل چندین ''سطل k'' برای سایر گره های 21+ باشد. این تضمین می کند که شبکه از همه گره های نزدیکترین منطقه اطلاع دارد. 

=== جستجوی شتاب ===
کادملیابرای تعیین فاصله از سنجش  ''[[یای انحصاری|XOR]]'' استفاده می کند. دو شناسه گره با هم یا یک شناسه گره و یک کلید باهم XOR می شوند و نتیجه این عمل ، فاصله بین آنها را تعیین می کند. برای هر بیت،تابع XOR  ، اگر دو بیت مساوی و یکی باشد صفر و اگر دو بیت با هم متفاوت باشند 1 را برمی گرداند. فواصل در سنجشهای XOR  از قانون [[نابرابری مثلثی|نابرابری مثلث]] پیروی می کنند: با توجه به اینکه A ، B و C [[رأس (هندسه)|راس]] (نقاط) یک مثلث هستند ، سپس فاصله A تا B کوتاهتر از (یا مساوی با) از مجموع فاصله A تا C تا B است. 

''سنجش XOR'' به کادملیا اجازه می دهد جداول مسیریابی را فراتر از بیت های واحد قرار دهد. گروه های بیت را می توان در ''سطل های K'' قرار داد. به گروه بیت ها پیشوند گفته می شود. برای پیشوند ''m-bit'' ، ''سطل'' 2 <sup>متر</sup> -1 <sup>کیلومتر</sup> وجود دارد. ''سطل K-'' گمشده ، بخش دیگری از درخت مسیریابی است که شامل شناسه گره است. پیشوند ''m-bit'' حداکثر تعداد جستجوها را از ''log <sub>2</sub> n'' تا ''log <sub>2 <sup>m</sup></sub> n کاهش می دهد'' . اینها مقادیر '''حداکثر''' هستند و مقدار متوسط به مراتب کمتر خواهد بود ، شانس یافتن گره در یک ''k-bucket'' که بیت های بیشتری را نسبت به پیشوند با کلید هدف به اشتراک می گذارد ، افزایش می دهد. 

گره ها می توانند از جدول پیشوندها در جدول مسیریابی خود استفاده کنند ، مانند شبکه Kad که توسط [[ای‌میول|eMule]] استفاده شده است. {{مدرک|date=January 2010}}   شبکه کادملیا حتی می تواند در اجرای برنامه های مسیریابی ، بصورت ناهمگن عمل کند که به قیمت بالارفتن هزینه پیچیدگی در تجزیه و تحلیل جستجوها است. 

== اهمیت علمی ==
در حالی که سنجش XOR برای درک کادملیا الزامی نیست ، اما در تجزیه و تحلیل پروتکل بسیار مهم است. حساب XOR یک [[گروه آبلی|گروه آبلی تشکیل]] می دهد که می تواند تجزیه و تحلیل بسته را انجام دهد. سایر پروتکل ها و الگوریتم های DHT به منظور پیش بینی رفتار و صحت شبکه ، نیاز به [[شبیه‌سازی کامپیوتری|شبیه سازی]] یا تحلیل رسمی پیچیده دارند. استفاده از گروه های بیت به عنوان مسیریابی اطلاعات ، الگوریتم ها را نیز ساده می کند. 

== تحلیل ریاضی الگوریتم ==
برای تجزیه و تحلیل الگوریتم ، یک شبکه کادملیارا در نظر بگیرید <math>n</math> گره ها با شناسه <math>x_1, \ldots, x_n</math> که هر کدام یک رشته طول دارند <math>d</math> که فقط از آنها و صفرها تشکیل شده است می توان آن را به عنوان یک [[درخت پیشوندی|trie]] مدل کرد که در آن هر برگ یک گره را نشان می دهد ، و مسیر برچسب زده شده از ریشه به یک برگ نشانگر ID آن است. برای یک گره <math>x \in \{x_1, \ldots, x_n\}</math> ، اجازه دهید <math>\mathcal D_i(x)</math> مجموعه گره ها (شناسه ها) باشد که پیشوند را با آنها به اشتراک می گذارد <math>x</math> طول <math>d - i</math> . سپس پر کردن <math>i</math> سطل چهارم <math>x</math> می توان به عنوان افزودن نشانگرها از برگ مدل شد <math>x</math> به <math>k</math> برگ (شناسه) به طور یکنواخت به طور تصادفی از <math>\mathcal D_i(x)</math> . بنابراین مسیریابی می تواند پرش در میان برگها در امتداد این نشانگرها باشد به گونه ای که هر مرحله تا حد ممکن به سمت شناسه هدف پیش می رود ، یعنی به طریقی حریص. 

اجازه دهید <math>T_{xy}</math> تعداد پرش های لازم برای رفتن از برگ باشد <math>x</math> به شناسه هدف <math>y</math> . فرض کنید که <math>x_1, \ldots, x_n</math> به طور قطعی از بین انتخاب می شوند <math>\{0,1\}^d</math> ثابت شده است که 

: <math>\sup_{x_1,\ldots, x_n} \, \sup_{x \in \{x_1,\ldots, x_n\}} \, \sup_{y \in \{0,1\}^d} \mathbb E[T_{xy}] \le (1+o(1)) \frac{\log n}{H_k} ,</math>

جایی که <math>H_k</math> هست <math>k</math> - شماره هارمونیک از آنجا که <math>H_k/\log k \to 1</math> مانند <math>k \to \infty</math> ، چه زمانی <math>k</math> بزرگ است <math>\mathbb E T_{xy}</math> از بالا به حدود محدود است <math>\log_k n</math> با این حال شناسه ها و هدف انتخاب می شوند. <ref>{{Cite journal|last=Cai|first=X. S.|last2=Devroye|first2=L.|year=2013|title=A Probabilistic Analysis of Kademlia Networks|journal=Algorithms and Computation|series=Lecture Notes in Computer Science|volume=8283|pages=711|arxiv=1309.5866|doi=10.1007/978-3-642-45030-3_66|isbn=978-3-642-45029-7}}</ref> این شهودی را توجیه می کند که فقط در کادملیا وجود دارد <math>O(\log n)</math> گره ها در جستجوی یک گره هدف تماس می گیرند. 

برای نزدیکتر کردن مدل به شبکه های واقعی کادملیا، <math>x_1, \ldots, x_n</math> همچنین می توان فرض کرد که به طور تصادفی و بدون جایگزینی از یکنواخت انتخاب می شود <math>\{0,1\}^d</math> . سپس می توان ثابت کرد که برای همه <math>x \in \{x_1, \ldots, x_n\}</math> و <math>y \in \{0,1\}^d</math> ، 

: <math>
\begin{align}
& T_{xy} \xrightarrow{p} \frac{\log n}{c_k},\\
& \mathbb E[T_{xy}] \to \frac{\log n}{c_k},
\end{align}
</math>

جایی که <math>c_k</math> یک ثابت است که فقط به آن بستگی دارد <math>k</math> با <math>c_k/H_k \to 1</math> مانند <math>k \to \infty</math> . بنابراین برای <math>k</math> بزرگ ، <math>\mathbb E T_{xy}/\log_k n</math> به یک نزدیک ثابت تبدیل می شود <math>1</math> . این بدان معنی است که تعداد گره ها برای جستجوی یک گره هدف نیاز به تماس دارند <math>\Theta(\log_k n)</math> به طور متوسط. <ref name="CaiDevroye2015">{{Cite journal|last=Cai|first=Xing Shi|last2=Devroye|first2=Luc|year=2015|title=The Analysis of Kademlia for Random IDs|journal=Internet Mathematics|volume=11|pages=1–16|arxiv=1402.1191|doi=10.1080/15427951.2015.1051674|issn=1542-7951}}</ref> 

== در شبکه های اشتراک فایل استفاده کنید ==
کادملیادر شبکه های [[اشتراک پرونده|اشتراک فایل]] استفاده می شود. با انجام جستجوی کلمات کلیدی کادملیامی توان اطلاعاتی را در شبکه اشتراک فایل پیدا کرد تا بارگیری شود. از آنجا که هیچ نمونه مرکزی برای ذخیره یک فهرست از پرونده های موجود وجود ندارد ، این کار به طور مساوی بین کلیه مشتری ها تقسیم می شود: اگر یک گره بخواهد یک فایل را به اشتراک بگذارد ، محتویات پرونده را پردازش می کند ، و از آن عددی ( [[تابع هش|هش]] ) محاسبه می کند. این پرونده را در شبکه اشتراک گذاری فایل شناسایی کنید. شناسه های هش و شناسه های گره باید به همان طول باشند. سپس چندین گره را که شناسه آنها نزدیک به هش است جستجو می کند و آدرس IP خاص خود را در آن گره ها ذخیره می کند. یعنی خود را به عنوان منبع این پرونده منتشر می کند. مشتری جستجوگر از کادملیابرای جستجوی شبکه برای گره ای استفاده می کند که شناسه آن کمترین فاصله را با هش پرونده داشته باشد ، سپس لیست منابعی را که در آن گره ذخیره شده است بازیابی می کند. 

از آنجا که یک کلید می تواند با بسیاری از مقادیر مطابقت داشته باشد ، به عنوان مثال بسیاری از منابع با همان پرونده ، هر گره ذخیره سازی می تواند اطلاعات مختلفی داشته باشد. سپس از همه گره های k نزدیک به کلید از منابع درخواست می شود. 

هش پرونده معمولاً از یک پیوند مخصوص آهنربای اینترنتی که در جای دیگر یافت می شود ، یا در یک پرونده فهرست بندی به دست آمده از منابع دیگر گنجانده می شود. 

جستجوهای نام فایل با استفاده از [[اصطلاح نمایه‌ای|کلمات کلیدی]] اجرا می شود. نام پرونده به کلمات تشکیل دهنده آن تقسیم می شود. هر یک از این کلمات کلیدی به همراه نام پرونده و هش پرونده در شبکه ذخیره شده و ذخیره می شوند. جستجو شامل انتخاب یکی از کلمات کلیدی ، تماس با گره با شناسه نزدیک به آن کلید واژه و بازیابی لیست نام فایلهای حاوی کلمه کلیدی است. از آنجا که هر نام پرونده در لیست هش خود پیوست شده است ، پس از آن پرونده انتخاب شده به روش عادی قابل دستیابی است. 

== پیاده سازی ها ==

=== شبکه ها ===
شبکه های عمومی با استفاده از [[الگوریتم]] کادملیا(این [[شبکه رایانه‌ای|شبکه]] ها با یکدیگر ناسازگار هستند): 

* [[پروژه اینترنت مخفی|I2P]] - یک لایه [[شبکه‌های همپوشان|شبکه با پوشش]] ناشناس. <ref>{{Cite web|url=https://geti2p.net/en/about/intro|title=Intro - I2P|website=geti2p.net}}</ref> 
* شبکه Kad - در اصل توسط جامعه [[ای‌میول|eMule]] توسعه یافته است تا جایگزین معماری مبتنی بر سرور شبکه eDonkey2000 شود . 
* [[اتریم (رمزارز)|اتریوم]] - پروتکل کشف گره در پشته شبکه [[زنجیره بلوکی|بلاکچین]].اتریوم مبتنی بر اجرای کمی اصلاح شده از کادملیااست. <ref>{{Cite web|url=https://github.com/ethereum/wiki|title=GitHub - ethereum/wiki: The Ethereum Wiki.|date=25 March 2019|publisher=}}</ref> 
* شبکه اورنت: با استفاده از KadC که یک کتابخانه C برای دستیابی به کادملیااست. (توسعه Overnet متوقف شده است)
* [[بیت‌تورنت|BitTorrent]] از DHT مبتنی بر اجرای الگوریتم کادملیابرای تورنتهای بدون ردیاب استفاده می کند.
* Osiris sps اوسیریس (تمام نسخه ها): برای مدیریت پورتال وب توزیع شده و ناشناس استفاده می شود. 
* [[رتروشر (نرم‌افزار)|Retroshare]] - بستر ارتباطی غیر متمرکز F2F با VOIP امن ، پیام رسانی فوری ، انتقال پرونده و غیره. 
* [[تاکس (پروتکل)|Tox]] - یک بستر پیام رسانی ، VoIP و چت تصویری کاملاً توزیع شده 
* [[ناتلا|Gnutella]] DHT - در اصل توسط LimeWire <ref name="mojito slyck">{{Cite web|url=http://www.slyck.com/story1235.html|title=Slyck News - LimeWire Regains Top Download.com Position|website=www.slyck.com|access-date=۲۳ دسامبر ۲۰۲۱|archive-date=۱۹ ژانویه ۲۰۱۹|archive-url=https://web.archive.org/web/20190119121353/http://www.slyck.com/story1235.html|url-status=dead}}</ref> <ref name="mojito wiki">{{Cite web|url=http://wiki.limewire.org/index.php?title=Mojito|archiveurl=https://web.archive.org/web/20090217070609/http://wiki.limewire.org/index.php?title=Mojito|title=Mojito - LimeWire|archivedate=17 February 2009|website=wiki.limewire.org}}</ref> برای تقویت پروتکل Gnutella برای یافتن مکان پرونده های جایگزین ، اکنون توسط سایر مشتری های gnutella استفاده می شود. <ref>{{Cite web|url=https://gtk-gnutella.svn.sourceforge.net/svnroot/gtk-gnutella/trunk/gtk-gnutella/ChangeLog|title=Gtk-gnutella changelog|last=|first=|date=|website=sourceforge.net|archiveurl=https://web.archive.org/web/20110723210536/https://gtk-gnutella.svn.sourceforge.net/svnroot/gtk-gnutella/trunk/gtk-gnutella/ChangeLog|archivedate=23 July 2011|accessdate=23 January 2010}}</ref> 
* IPFS - یک سیستم فایل متشکل از همسالان مبتنی بر libp2p. <ref>{{Cite web|url=https://github.com/ipfs/papers/raw/master/ipfs-cap2pfs/ipfs-p2p-file-system.pdf|title=IPFS Paper|publisher=}}</ref> 
* TeleHash یک پروتکل شبکه مش است که از کادملیابرای حل و فصل ارتباط مستقیم بین طرفین استفاده می کند. <ref>{{Cite web|url=http://redecentralize.org/interviews/2013/10/17/07-jeremie-telehash.html|title=#7: Jeremie Miller - TeleHash|accessdate=2016-03-12}}</ref> 
* iMule - [[نرم‌افزار سودمند|نرم]] افزار [[نرم‌افزار سودمند|ابزار]] [[اشتراک پرونده|اشتراک فایل]] برای [[پروژه اینترنت مخفی|I2P]] . 
* OpenDHT - کتابخانه ای که اجرای کادملیارا ارائه می دهد ، توسط [[جمی (نرم‌افزار)|جامی]] و دیگران استفاده می شود. 
* [[گنونت|GNUnet]] - پشته شبکه جایگزین برای ایجاد برنامه های توزیع شده ایمن ، غیرمتمرکز و حفظ حریم خصوصی. از نسخه تصادفی کادملیابه نام R5N استفاده می کند <ref>{{Cite web|url=https://git.gnunet.org/bibliography.git/plain/docs/nss2011.pdf|title=R5N: Randomized Recursive Routing for Restricted-Route Networks}}</ref> 

== همچنین ببینید ==

* [[شبکه آدرس‌دهی محتوا|شبکه آدرس دهی محتوا]] 
* [[کورد (نظیر به نظیر)|کورد (DHT)]]
* [[تاپستری ( شبکه)|تاپستری]](DHT) 
* [[پاستری ( شبکه)|پاستری]](DHT) 
* [[کوورد (شبکه)|کوورد]]

== منابع ==
{{پانویس}}

== پیوند به بیرون ==

* [http://xlattice.sourceforge.net/components/protocol/kademlia/specs.html پروژه های Xlattice] مشخصات و تعاریف Kademlia. 
[[رده:مسیریابی رایانه‌ای]]
[[رده:درهم‌سازی]]
[[رده:معماری شبکه]]
[[رده:اشتراک پرونده]]
[[رده:ذخیره‌سازی داده توزیع‌شده]]
[[رده:معرفی‌شده‌های مرتبط با رایانه در ۲۰۰۲ (میلادی)]]
[[رده:صفحات با ترجمه بازبینی‌نشده]]