Lock-free concurrent binomial heaps

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