CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Competitive Freshness Algorithms for Wait-free Data Objects

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)) ; Phuong Ha (Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers)) ; Philippas Tsigas (Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers))
Göteborg : Chalmers University of Technology, 2005. - 11 pages s.
[Rapport]

Wait-free concurrent data objects are widely used in multiprocessor systems and real-time systems. Their popularity results from the fact that they avoid locking and that concurrent operations on such data objects are guaranteed to finish in a bounded number of steps regardless of the other operations interference. The data objects allow high access parallelism and guarantee correctness of the concurrent access with respect to its semantics. In such a highly-concurrent environment, where write-operations update the object state concurrently with read-operations, the age/freshness of the state returned by a read-operation is a significant measure of the object quality. In this paper, we first propose a freshness measure for wait-free concurrent data objects. Subsequently, we model the freshness problem as an online problem and present two algorithms for the problem. The first one is an optimal deterministic algorithm with freshness competitive ratio $\sqrt{\alpha}$, where $\alpha$ is a function of execution-time upper-bound of wait-free operations. The second one is a competitive randomized algorithm with freshness competitive ratio $\frac{\ln \alpha}{1 + \ln 2 - \frac{2}{\sqrt{\alpha}}}$.

Nyckelord: wait-free synchronization, online algorithms, concurrent data structures



Denna post skapades 2006-08-25. Senast ändrad 2015-02-11.
CPL Pubid: 8190

 

Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)
Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)
Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers) (2005-2007)

Ämnesområden

Information Technology

Chalmers infrastruktur

Relaterade publikationer

Denna publikation ingår i:


Reactive Concurrent Data Structures and Algorithms for Synchronization


Ingår i serie

Technical report - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University 2005:18