Fast timing-based algorithms

Rajeev Alur, Gadi Taubenfeld

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

ملخص

Summary. Concurrent systems in which there is a known upper bound Δ on memory access time are considered. Two prototypical synchronization problems, mutual exelusion and consensus, are studied, and solutions that have constant (i.e. independent of Δ and the total number of processes) time complexity in the absence of contention are presented. For mutual exclusion, in the absence of contention, a process needs only five accesses to the shared memory to enter its critical section, and in the presence of contention, the winning process may need to delay itself for 4 . Δ time units. For consensus, in absence of contention, a process decides after four accesses to the shared memory, and in the presence of contention, it may need to delay itself for A time units.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)1-10
عدد الصفحات10
دوريةDistributed Computing
مستوى الصوت10
رقم الإصدار1
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1996

بصمة

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

قم بذكر هذا