Efficient and low-cost fault tolerance for web-scale systems [Elektronische Ressource] / vorgelegt von Marco Serafini

E cient and Low-Cost Fault Tolerancefor Web-Scale SystemsVom Fachbereich Informatik der Technischen Universit at DarmstadtgenehmigteDissertationzur Erlangung des akademischen Gradeseines Doktor rerum naturalium (Dr. rer. nat.)vorgelegt vonDott. Marco Sera niaus Arezzo, ItalienReferenten:Prof. Neeraj Suri, Ph.D.Prof. Rodrigo Rodrigues, Ph.D.Datum der Einreichung: 17. Juni 2010Datum der mundlic hen Prufung: 16. September 2010Darmstadt 2010D17iiSummaryOnline Web-scale services are being increasingly used to handle critical per-sonal information. The trend towards storing and managing such information onthe \cloud" is extending the need for dependable services to a growing range of Webapplications, from emailing, to calendars, storage of photos, or nance. This moti-vates the increased adoption of fault-tolerant replication algorithms in Web-scalesystems, ranging from classic, strongly-consistent replication in systems such asChubby [Bur06] and ZooKeeper [HKJR10], to highly-available weakly-consistent+ +replication as in Amazon’s Dynamo [DHJ 07] or Yahoo!’s PNUTS [CRS 08].This thesis proposes novel algorithms to make fault-tolerant replication moree cient, available and cost e ective. Although the proposed algorithms aregeneric, their goals are motivated by ful lling two major needs of Web-scale sys-tems.