کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10330632 | 686051 | 2005 | 45 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Time and space optimal implementations of atomic multi-writer register
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
This paper addresses the wide gap in space complexity of atomic, multi-writer, multi-reader register implementations. While the space complexity of all previous implementations is linear, the lower bounds are logarithmic. We present three implementations which close this gap: The first implementation is sequential and its role is to present the idea and data structures used in the second and third implementations. The second and third implementations are both concurrent, the second uses multi-reader physical registers while the third uses single-reader physical registers. Both the second and third implementations are optimal with respect to the two most important complexity criteria: Their space complexity is logarithmic and their time complexity is linear.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 200, Issue 1, 1 July 2005, Pages 62-106
Journal: Information and Computation - Volume 200, Issue 1, 1 July 2005, Pages 62-106
نویسندگان
Amos Israeli, Amnon Shaham,