A distributed replicated database system having a plurality of federated database systems and methods of updating and reading database records from the distributed replicated database system are disclosed. Each federated database system contains a complete copy of a database. Moreover, each federated database system comprises at least one server divided into at least one logical partition. A logical partition contains records of the database and all logical partitions in a federated database system cumulatively stores all records in the database. A data structure is maintained which indicates whether the records in a given logical partition are up-to-date. When an update or insert request is received, the data structure is modified to indicate that all logical partitions storing a copy of the record to be updated, or partitions into which the new record is to be inserted, are not up-to-date. When the record has been updated or inserted, the data structure is modified to indicate that the logical partition storing the record is up-to-date. When a read request is received, the record is read from an up-to-date logical partition storing the record.