We present a formal specification of primary-backup. We then prove lower bounds on the degree of replication, failover time and worst-case response time to client requests assuming different failure models. Finally, we outline primary-backup protocols and indicate which of our lower bounds are tight. Keywords: Fault-tolerance, reliability, availability, primary-backup, lower bounds, optimal protocols.