The Prime Replication System

About Us












Secure Spread

    Prime: Byzantine Replication Under Attack

Home | Overview | Software | Fundings | Documentation | License | Publications | Credits


Prime is a Byzantine fault-tolerant replication system whose goal is to provide a meaningful level of performance even after some of the replication servers have been compromised. Like previous Byzantine fault-tolerant replication protocols, Prime meets Safety (consistency of the correct replicas) and Liveness (the eventual execution of each update) as long as no more than f out of 3f+1 replicas are compromised and the network is sufficiently stable. Unlike previous protocols, Prime is also designed to meet a stronger performance guarantee, which we call Bounded-Delay. Bounded-Delay limits the amount of performance degradation that can be caused by malicious servers. Intuitively, Prime forces any leader that remains in power to meet a threshold level of performance, where the threshold is a function of the message delays between the correct servers in the system, which cannot be arbitrarily increased by the malicious servers.

Prime supports proactive recovery, diversity, and state transfer. Prime servers can be periodically rejuvenated to clean the system from potentially undetected intrusions. The MultiCompiler described here can be used to obfuscate the code layout of Prime servers in order to increase the resiliency of the system. The MultiCompiler uses a 64-bit random number to generate different variants of an application. A different version of a Prime server can be generated after each rejuvenation. In this way, if an adversary attacks all the servers in parallel, the probability to defeat more than f servers is low. After rejuvenation, a Prime server also validates the contents of the state on the disk with the help of other correct replicas and recovers a clean copy of the state if necessary. Subsequently, the rejuvenated replica collects all the client updates necessary to catch up and resume the execution. The state and update transfer protocols are guaranteed to meet Safety because they are coordinated by a quorum of correct replicas.

Prime can be configured to make use of Spines, an overlay network developed at Johns Hopkins (see This can be useful for testing wide-area topologies and placing bandwidth and latency constraints on the links between servers.

Prime was created at Johns Hopkins University by Yair Amir, Jonathan Kirsch, John Lane, and Marco Platania.

Special thanks to Brian Coan for major contributions to the design of the Prime algorithm, and Jeff Seibert for major contribution to the View Change protocol.


A version of Prime suitable for evaluating the performance of the protocol in both fault-free and under-attack executions can be downloaded here. The code was written in C and runs on Linux. Prime was tested with version 3.5 of the MultiCompiler, which is included in the Prime software package. Please refer to the MultiCompiler website for further releases.


  • Version 2.0 - September 17, 2014
  • Version 1.1 - December 07, 2013
  • Version 1.0 - May 04, 2010


Partial funding for Prime research was provided by the Defense Advanced Research Projects Agency (DARPA) and the National Science Foundation (NSF). Prime is not necessarily endorsed by DARPA or the NSF.


Prime may be freely used and distributed under some conditions. Please review the license agreement for more details.

Related Publications

Questions or comments to:
TEL: (410) 516-5562
FAX: (410) 516-6134
Distributed Systems and Networks Lab
Computer Science Department
Johns Hopkins University
3400 N. Charles Street Baltimore, MD 21218-2686