Replication is a common technique used to design reliable distributed systems by masking defective components. To cope with the requirements of modern Internet applications, replication protocols must allow for throughput scalability and dynamic reconfiguration, that is, on-demand replacement or provisioning of system resources. This paper describes Elastic Paxos, a new dynamic atomic multicast protocol that fulfills these requirements. Elastic Paxos allows to dynamically add and remove resources to an online partially replicated state machine. We implemented Elastic Paxos and evaluated its performance in OpenStack, a cloud environment. We demonstrate its practicality to dynamically scale up and down a partially replicated data store with it and to reconfigure a distributed system.