A system that implements a data storage service may store data on behalf of storage service clients. The system may maintain data in multiple replicas that are stored on respective computing nodes in the system. Updates to the stored data and to the membership of replica groups are propagated as replicated log records. A replica receiving a log record may compare metadata in the received log record to corresponding metadata in a log record that was previously appended to its log to determine a response. The metadata may include a sequence number, a lock generation identifier, an epoch identifier, or an indication of an epoch change. The replica may append the received log record to its log, drop the received log record, or cache the received log record for future use. If a log conflict indicates an invalid log stream branch, one or more log records may be deleted.