Byzantine fault tolerant (BFT) protocols are replication-based solutions to the problem of tolerating the arbitrary failures of software and hardware components. The essential assumption for replication is independence of failures. In this paper, we categorize four different failure independence levels that could be obtained from the cloud. Not surprisingly, providing more level of independence comes with the cost of more delays and less bandwidth. We report on our experiments to identifying the most appropriate BFT protocol for each level.