%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%  BFTSim Release v0.1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%  April 2008          %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


Contributors
------------

This implementation was written by Atul Singh. 
This work was first published as "BFT Protocols under Fire. NSDI 2008."
Atul Singh (Rice/MPI-SWS), Tathagata Das (IIT Kharagpur), Petros Maniatis 
(Intel Research Berkeley), Peter Druschel (MPI-SWS), Timothy Roscoe (ETH-Zurich)

Copying
-------

    Copyright (C) 2008, 2009 Atul Singh

    These programs are free software; you can redistribute them and/or modify
    them under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    These programs are distributed in the hope that they will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with these programs; if not, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.



Source Info
-------------
BFTSim is built upon ns2 and P2. Please look at our paper for the architecture.
This is a pre-alpha release and has minimal to no documentation.


1. Directory structure: Source is located in bftsim/src
  -- ns2: contains the usual ns2 and our modifications
  -- P2: contains the P2 version 1.1.1.1, released in July 2007. 
  -- Note that you may need to install different libraries to correctly install both ns and P2. 
     Please look at their source directories for the READMEs and appropriate instructions.
  -- scripts: contains various scripts to run experiments as well as process the data

2. scripts directory contains our implementations of three protocols in OverLog. Please look
   at PBFT.olg, QU.olg, Zyzzyva.olg and Zyzzyva5.olg.

3. Compilation
  -- run $./compile
     This will first compile P2 source, then create a library of P2,
     which is used to compile ns2 source.
     It will then produce bftsim executable.
     We have run BFTSim on linux 2.6.24.2.1 with AMD64 bit processor.
     
4. Running the experiments
  -- go to scripts directory
  -- To reproduce our NSDI results, look at run_exp.pl and below at "running an experiment".
  -- All experiments are computation heavy, typically requiring 100% of CPU. So you may want 
     to run separate experiments on separate machines.

5. Bug reports
  -- This is a pre-alpha release and most probably has lot of bugs. Please report
     them by sending an email to atuls@cs.rice.edu.


Running an experiment
---------------------
At a high level, BFTSim expects two parameters: input protocol specification in Overlog
and a input network specification in a tcl file. For running a wide range of experiments,
we allow command line parameters to vary the configurations specified in either the protocol
specification (such as quorum size, F, request and response size, etc.) or in the network
ns2 specification (such as link latency, bandwidth, loss rates, etc.). 

1. Go to src/scripts and look at run_exp.pl
2. run "perl run_exp.pl --outdir <x> --protocol <y> --expr <z>"
   X is the location where output will be stored, y is the protocol id (0 for PBFT, 1 for Q/U, 2
   for Zyzzyva, and 3 for Zyzzyva5). Z identifies which experiment to run. Look at run_expr.pl to 
   know what are the different experiments you can run.
3. Vary the parameters in the run_exp.pl to run different set of experiments.
4. There is a parameter TIMETOEXIT that controls how long you want to run a given experiment.
5. Update LD_LIBRARY_PATH adding ./../tk8.4.14/unix/ so that ns can run.
6. We have provided two tcl scripts: tcl_baseline and tcl_heter. First one creates a generic
   network star topology which can take as parameters the latency, bandwidth, and loss characteritics
   for client links as well as replica links. 

Specifying compute operations
----------------------------
One of the core component of BFTSim is to simulate compute operations, such as calculating
digest of a message or calculating MAC or an authenticator. We use following built-in functions
to allow the programmer to specify what operation to perform on per rule basis:

1. f_mac(F, PROTOTOL_TYPE, MAC_ALGO), f_auth(F, PROTOCOL_TYPE, MAC_ALGO)
   Returns a double value to suggest the time it would take to calculate a MAC or authenticator
   Input: (i) F: number of faults simulated
   	  (ii) PROTOCOL_TYPE: whether this is a 3f+1 or 5f+1 type of protocol
	  (iii) MAC_ALGO: 1 for UMAC and 2 for HMAC

2. f_digest(COUNT, A, B, C)
   Uses MD5.
   This is used when each of the fields is a base data type, like int, double, string etc.
   Returns a double value to suggest the time it would take to calculate a digest over COUNT fields
   and A, B, and C are the fields
   Input: (i) COUNT: how many fields
   	  (ii) A, B, C: fields of the tuple

3. f_digestraw(SIZE)
   Uses MD5.
   This is used when the tuple field is a compound data type, for example a data structure or a hash.
   Returns a double value to suggest the time it would take to calculate a digest over data of size SIZE.
   Input: SIZE is the size of the data in bytes over which the digest needs to be taken.

4. f_network(COUNT, A, B, C)
   This is used when each of the fields is a base data type, like int, double, string etc.
   Returns a double value to suggest the time it would take to send data over the network, consisting of
   COUNT field, and A, B, and C are the fields
   Input: (i) COUNT: how many fields
   	  (ii) A, B, C: fields of the tuple

5. f_networkraw(SIZE)
   This is used when the tuple field is a compound data type, for example a data structure or a hash.
   Returns a double value to suggest the time it would take to send data of size SIZE.
   Input: SIZE is the size of the data in bytes over which the digest needs to be taken.


Limitations
---------------
While we have tested BFTSim and our implementations of PBFT, Q/U, Zyzzyva/Zyzzyva5 in various
settings, there are currently following limitations --
1. View change logic of both PBFT and Zyzzyva has not been tested extensively.
2. Contention logic of Q/U has not been tested extensively.
3. We have not yet evaluated the multicast and broadcast facilities of ns2. However, BFTSim takes
   into account the computation benefits of multicast by charging for a single send when doing multicast.
4. Currently, we are not able to scale the client population to more than 1000 nodes. This is due to
   P2 dataflows that are created, which takes memory as well as higher processing due to large number of events. 
5. We have used UDP so far and plan to use reliable transports such as TCP.
6. Upgrade to latest P2 release.

We are currently working towards removing these limitations.