Byzantine Techniques II Presenter: ios Piliouras Partly based on slides by Justin W. Hart & Rodrigo Rodrigues Papers ?Practical Byzantine Fault Tolerance . Miguel Castro et. al. (OSDI 1999) ?BAR Fault Tolerance for Cooperative Services . Amitanand S. Aiyer, et. al. (SOSP 2005) Motivation ?Computer systems provide crucial services server client Problem ?Computer systems provide crucial services ?Computer systems fail –natural disasters –hardware failures –software errors –malicious attacks Need highly-available services client server Replication unreplicated service client server Replication replicated service client server replicas unreplicated service client server Replication algorithm: ? masks a fraction of faulty replicas ? high availability if replicas fail “independently ” Assumptions are a Problem ?Replication algorithms make assumptions: –behavior of faulty processes –synchrony –bound on number of faults ?Service fails if assumptions are invalid Assumptions are a Problem ?Replication algorithms make assumptions: –behavior of faulty processes –synchrony –bound on number of faults ?Service fails if assumptions are invalid –attacker will work to invalidate assumptions Most replication algorithms assume too much Contributions ?Practical replication algorithm: –weak assumptions ? tolerates attacks – good performance ?Implementation –BFT: a generic replication toolkit –BFS: a replicated file system ?Performance evaluation BFS is only 3% slower than a standard file system Talk Overview ?Problem ?Assumptions ?Algorithm ?Implementation ?Performance ?Conclusions