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

Online strategies for backups

Peter Damaschke (Institutionen för datavetenskap, Algoritmer)
Theoretical Computer Science (0304-3975). Vol. 285 (2002), 1, p. 43-53.
[Artikel, refereegranskad vetenskaplig]

We consider strategies for backups from the viewpoint of competitive analysis of online problems. We concentrate upon the realistic case that faults are rare, i.e. the cost of work between two faults is typically large compared to the cost of one backup. Instead of the (worst-case) competitive ratio we use a refined and more expressive quality measure, in terms of the average fault frequency. The interesting matter is, roughly speaking, to adapt the backup frequency to the fault frequency, while future faults are unpredictable. We give an asymptotically optimal deterministic strategy and propose a randomized strategy whose expected cost beats the deterministic bound.

Nyckelord: online problems, nonstandard competitive analysis, backup costs, randomized strategy

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


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för datavetenskap, Algoritmer (2002-2004)


Information Technology

Chalmers infrastruktur