Byzantine Fault Tolerant Cooperative Caching Raluca Ada Popa, James Cowling, Barbara Liskov

Byzantine Fault Tolerant Cooperative Caching

• Raluca Ada Popa, James Cowling, Barbara Liskov

• Summer UROP

• CSAIL, MIT

Outline

• Introduction

• Motivation

• System Description

• Discussion

• Conclusions

Introduction

• Cooperative caching: multiple peers coordinate their caches

• Efficiency
• Scalability

• Byzantine client: any client that does not behave properly

• Our contribution is to add Byzantine fault tolerance to cooperative caching

Motivation

• Cooperative caching is useless with Byzantine clients

• Clients can provide false data

• Our system is useful for a distributed safe storage system

System Setting

• Many clients request/modify pages

• Some are Byzantine

• A storage server

• Runs BFT

• Clients commit transactions at the server

• Clients implement cooperative caching

System Overview

• Optimistic approach

• Few Byzantine clients in the common case
• Reputation system for efficiency

• Exploit locality

• Organize peers in locality regions

Optimistic Approach

• Assumes speculatively that clients are non-Byzantine

• Upon commit, the server checks if data used was up-to-date

• Rolls back if not

• Check is based on hashes

• Reputation system reduces the number of aborts

Locality

• Split peers in locality regions based on their coordinates (eg. Vivaldi)

• Look up a page in own locality region first

• Rationale

• Common case: hot pages are in locality region
• Fast fetch of data

Page Lookup

• Consistent hashing function in each locality region:

• Peer with metadata for Page ID knows which peers store the page

• Provides replication

Maintaining Metadata

• Each client informs the appropriate metadata peer when fetching from the server, updating, or removing a page

• Metadata peers communicate

• Server sends periodic invalidation streams (e.g. peer membership)

Page Fetch Walk-through

• Look in local cache

• Ask the metadata node in the locality region

• Ask the server

Reputation System

• Each client maintains reputation scores

• Initial debit
• Debit increased/decreased depending on behavior

• Is based on information from the server upon commit

• Fetch from highest reputation peer

• Clients sign messages

Discussion

• Byzantine resilience

• Reputation system
• Last check performed at server

• Efficiency

• Three short network delays

• Scalability

• Server is offloaded

Project Status

• Prototype is designed and implemented

• Need to evaluate

• Efficiency of the reputation system
• Average fetch time

Conclusions

• First Byzantine fault tolerant cooperative caching system

• Efficient and scalable

• We hope it will show good evaluation results

Thank You

• Questions?