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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1996

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Fast timing-based algorithms'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי