Solutions to HW05: hw5-solutions.pdf

# 1. Snapshots

Do Exercise 13.11 from LynchBook.

# 2. Snapshots and consensus

Do Exercise 13.18 from LynchBook.

# 3. Fetch-and-permute objects and consensus

A **fetch-and-permute** object of size k (FAP_{k}) has as its state a permutation of the integers {1,...,k}, and supports k! distinct operations FAP(π), one for each permutation π, where each such operation replaces the old state s with π(s) and returns the old state. Prove the best upper and lower bounds you can on the consensus number of a fetch-and-permute object as a function of k, where the consensus number for the purposes of this problem is defined as the maximum number of processes n for which it is possible to solve wait-free consensus using any number of FAP_{k} objects and any number of registers.