کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952020 | 1442001 | 2017 | 30 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Two-process synchronization
ترجمه فارسی عنوان
هماهنگ سازی دو مرحله ای
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم های توزیع شده، حافظه مشترک، هماهنگ سازی، خطی سازگاری،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Aguilera, Gafni and Lamport introduced and solved the mailbox problem in [3], which can be used to speed-up interactions between a processor and a device. They provide a mailbox algorithm with “flag registers” of size 14 and space complexity Î(nlogâ¡n), and they conjecture that a solution with logarithmic space complexity exists. We prove this conjecture by presenting such a mailbox algorithm. We prove that the space complexity of our mailbox algorithm is optimal. The size of its flag registers is reduced to 4, which matches a lower bound established by Aguilera et al. In the same paper, Aguilera et al. also pointed out that the mailbox problem can be solved by means of a more general problem: the signaling problem. They presented a non-blocking solution to the signaling problem, and asked whether a wait-free solution exists. We solve this question with a bounded wait-free signaling algorithm, and we prove its correctness. A related problem is the N-buffer problem introduced by Lamport. Aguilera et al. employ their mailbox algorithm and provide a first solution to the N-buffer problem with flag registers of constant size. The drawback of their solution is its space complexity which is unbounded. We show how our signaling algorithm can be used to solve the N-buffer problem with constant-size flags and optimal space complexity.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 688, 6 August 2017, Pages 2-23
Journal: Theoretical Computer Science - Volume 688, 6 August 2017, Pages 2-23
نویسندگان
Uri Abraham, Gal Amram,