Large-scale applications in many different fields can now be executed on platforms based on Internet-connected PCs volunteered by their owners. These are usually loosely coupled applications like search for extraterrestrial intelligence [ACK+02] or bioinformatics applications [TAKI06] that can benefit from a large number of relatively slow machines. The scheduling of their tasks is also quite easy and their performance comparable with those of large supercomputers or datacenters. However, this “simplicity” has a cost. Faults often occurs that make strong fault tolerant algorithms mandatory. These algorithms usually use replication of tasks over different nodes.