Time-adaptive algorithms for synchronization

Rajeev Alur, Hagit Attiya, Gadi Taubenfeld

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء


We consider concurrent systems in which there is an unknown upper bound on memory access time. Such a model is inherently different from asynchronous model where no such bound exists, and also from timing-baaed models where such a bound exists and is known a priori. The appeal of our model lies in the fact that white it abstracts from implementation details, it is a better approximation of real concurrent systems compared to the asynchronous model. Furthermore, it is stronger than the asynchronous model enabling us to design algorithms for problems that are unsolvable in the asynchronous model. Two basic synchronization problems, consensus and mutual exclusion, are investigated in a shared memory environment that supports atomic registers. We show that Θ(Δ ,logΔ/loglogΔ ) is an upper and lower bound on the time complexity of any consensus algorithm, where A is the (unknown) upper bound on memory access time. For the mutual exclusion problem, we design an efficient algorithm that takes advantage of the fact that some upper bound on memory access time exists. The solutions for both problems are even more efficient in the absence of contention, in which case their time complexity is a con- Stant.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفProceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994
ناشرAssociation for Computing Machinery
عدد الصفحات10
رقم المعيار الدولي للكتب (الإلكتروني)0897916638
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 23 مايو 1994
منشور خارجيًانعم
الحدث26th Annual ACM Symposium on Theory of Computing, STOC 1994 - Montreal, كندا
المدة: ٢٣ مايو ١٩٩٤٢٥ مايو ١٩٩٤

سلسلة المنشورات

الاسمProceedings of the Annual ACM Symposium on Theory of Computing
مستوى الصوتPart F129502
رقم المعيار الدولي للدوريات (المطبوع)0737-8017


!!Conference26th Annual ACM Symposium on Theory of Computing, STOC 1994

ملاحظة ببليوغرافية

Publisher Copyright:
© 1994 ACM.


أدرس بدقة موضوعات البحث “Time-adaptive algorithms for synchronization'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا