PineWikiSolutions to HW05: hw5-solutions.pdf
Snapshots
Do Exercise 13.11 from LynchBook.
Snapshots and consensus
Do Exercise 13.18 from LynchBook.
Fetch-and-permute objects and consensus
A fetch-and-permute object of size k (FAPk) 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 FAPk objects and any number of registers.