The major purpose of a Grid is to federate multiple powerful resources into a single virtual entity which can be accessed transparently and efficiently by external users. As a Grid is usually an unreliable system involving heterogeneous resources located in different geographical domains, distributed and fault-tolerant resource allocation services have to be provided. In particular when a crash occurs tasks have to be reallocated quickly and automatically, in a completely transparent way from the users' point of view. This paper presents Paradis, an adaptive middleware based on a set of basic agreement services that has been integrated within an experimental Grid dedicated to genomic applications.