【正文】 read B Request timestamps Propose timestamp Read at timestamp Return fragments d1 d2 Find timestamps Read at timestamp James Hendricks, 10 Read protocol mon case Request timestamps and optimistically read fragments Return fragments and timestamp B d1 d2 James Hendricks, 11 Issue 1 of 3: Wasteful encoding Erasure code m + 2 f Hash m + 2 f Send to each server But only wait for m + f responses ? This is wasteful! d1 d2 d3 d4 B m: Fragments needed to decode f: Number of faults tolerated James Hendricks, 12 Solution 1: Partial encoding Instead: Erasure code m+f Hash m+f Hear from m+f Pro: Compute f fewer frags Con: Client may need to send entire block on failure Should happen rarely d1 d2 d3 B James Hendricks, 13 Issue 2: Block must be unique Fragments must prise a unique block ? If not, different readers read different blocks Challenge: servers don’t see entire block ? Servers can’t verify hash of block ? Servers can’t verify encoding of block given hashes of fragments James Hendricks, 14 Sol’n 2: Homomorphic fingerprinting Fragment is consistent with checksum if hash and homomorphic fingerprint [PODC07] match Key property: Block decoded from consistent fragments is unique hash4 hash3 hash2 hash1 fp2 fp1 d′4 hash4′ fp4 fp4′ James Hendricks, 15 Issue 3: Write ordering Reads must return most recently w