Do not distribute. Thank you for following me over the summer!

Do not use without permission. If you notice any issues in the proofs feel free to contact me.

The lower bound for algorithms which have optimal reads at the moment is much lower than the upper bound provided by the algorithms. Currently the best known algorithms for this problem need k-1 registers, while the lower bound is on the order of log2(k) (at least for the atomic case). In my opinion the algorithms are optimal, but there needs to be more work to know for certain

At the moment my intuition for thinking that the linear amount of registers is necessary is based on the fact that the physical writes in a logical WRITE must be "invisible" until the final value for the WRITE is written into the register. so if the values that a READ was going to read were "010" and then a logical WRITE wanted to change this value to "101" then if the WRITE wrote to the same registers that the READ was going to read then the read could read any of the sequences: "110", "000", "011", "111", "100", "001", "010", or "101". Clearly this is more than the two possible sequences which would be valid in Regularity or Atomicity (consistency conditions for registers) so only using 3 (log2(k)) registers for 8 (k) values is a no go. Seeing this however is much easier than actually proving that you need k-1 registers to properly implement it, even harder than that is then showing that every case, not just k=8 needs k-1 registers. However I think this kind of idea is a good building block to understanding why k-1 registers might be necessary. Hopefully in the future I'll have a concrete mathematical reason for why k-1 registers are needed, or who knows, maybe the tree algorithm (which uses k-1 registers) can be improved to use less physical registers. Either way it should be an interesting journey.

Following the previous two posts we can now show that every Algorithm where the READ takes at most log2(k) steps to implement a k-valued register will have a worst case logical WRITE which needs to use log2(k) physical WRITES to change the value of the register.

Following the groundwork laid out in the previous two posts we can show this as so.

Let x_1 be the first register read in the READ of each execution in S.  Note that in half of the elements of S, the value read from x_1 in the READ must be different from the initial value of x_1, in order to be able to reach all the leaves on that half of the decision tree.  In other words, the WRITE writes to x_1 in half the executions in S.  Let S_1 be the subset of S consisting of the executions in which the WRITE writes x_1; note that |S_1| = k/2.  Now let x_2 be the register corresponding to the root of subtree in which x_1 was written.  A similar argument shows that in half the executions in S_1, the value read from x_2 in the READ must be different from the initial value of x_2.  Let S_2 be the subset of S_1 consisting of the executions in which the WRITE writes to x_2; note that |S_2| = k/2^2.  Continuing this way we obtain S_{log_2 k}, which is of size 1, in which the WRITE writes to x_1, x_2, ..., x_{log_2 x}.  By Lemma 2, each of these registers is distinct and thus the WRITE writes to at least log_2 k registers.

Here is a formal proof for the intuitive idea that if an algorithm simulates a k-valued logical register who's logical READs only use log2(k) physical reads, none of the physical reads in a logical READ can read the same value more than once. The intuition is that the amount of physical reads is limited to the point that if any one physical read is "wasted" it becomes impossible to implement a proper register.

The proof starts off with a more formal scenario definition than the previous post, which was thought up by Dr. Jennifer Welch of Texas A&M University. The definition goes as follows (note RP=Read Process and WP=Write Process):

Let the value set be V = {v_i | 0 <= i < k}.
Consider the following set S of executions of A:
sigma_i = WRITE(v_i) alpha_i ACK READ_1 beta_i RETURN(v_i)
where only the WP takes steps in alpha_i and only RP_1 takes steps in beta_i, 0 <= i < k

Suppose in contradiction that the READ in sigma_i reads the same register more than once, for some i.  Let x be the first register that RP_1 reads twice, say the a-th read and the b-th read, with b > a. Consider the node in the decision tree for the b-th read in the path for sigma_i.  This node must have two children since the decision tree is complete by the proof in the previous post.  Consider a root-to-leaf path "pi" in the decision tree that forks off from the path corresponding to sigma_i at this node. 
From the previous post, there is a one-to-one correspondence between root-to-leaf paths in the decision tree and the set of executions and so "pi" corresponds to sigma_j in S, for some j != i. 

However, it is not possible for sigma_i and sigma_j to read different values from x at the b-th read since the only process that is taking steps during the READs is RP_1:  even if RP_1 writes to x during the READ, it will write the same value in sigma_i as in sigma_j, as nothing differs in those two executions until reaching the b-th read.  showing that no two physical reads can read the same register more than once.

It is well known that  any algorithm that implements a k valued register out of binary registers will occur at least one worst case READ which need to read log2(k) registers. However there has never been an clear analysis (for best/average case) for algorithms who's worst case logical READ is log2(k), or in other words is optimal. This post shows that if an algorithm has optimal logical reads, then all logical READs must use exactly log2(k) physical reads for an any consistency condition proposed by Leslie Lamport in "On Interprocess Communication."

A general model of any logical READ routine goes as follows: each logical READ starts by reading a register, determined by a combination of the algorithm and its current state; after reading that initial register the Read Process (RP) will make a decision of what register to read next, and it can this use this information to decide what process to read following that and so on. This behavior can be modeled as a decision tree where each node is a physical read, and each node has two children representing the next register to read based on the information contained in the parent node. Each path in the tree from the root to a leaf represents a distinct READ where the leaf reached can be directly mapped on to one value in the given Value Set, V. As a result of each READ using ≥log2(k) physical reads, the tree has a maximum height of log2(k). Clearly to implement a k-ary register the decision tree must have at least k many leaves, otherwise the decision tree will not be able to map to every value in V. Now noticing that the only way for a binary tree with ≥log2(k) levels to have k many leaves is be a full tree of height log2(k), this implies that each path (likewise logical READ) must visit log2(k) many nodes (likewise read log2(k) binary registers), showing that each logical READ must always read exactly log2(k) physical registers if no logical READ can do more than log2(k) physical reads.

Rough Draft. Please do not distribute without contacting me

A well known way of implementing a k valued regular register is called the tree algorithm. To start off with a regular register is a special type of register, a way to share a held number, which has some useful properties as follows: if a read of the register doesn't overlap a write the read must return the previous written value, and if a read overlaps a write it will either return the new value or the previously written value. The tree algorithm specifically provides a way to take several binary regular registers, and put them together to create a new register that can represent k many values, instead of 2, while still maintaining the regular constraint.

Recently a paper that expands on the tree algorithm has been published but needs on the order of k^2 many binary registers and 2lg(k) physical reads for one logical read, compared to the original algorithm's k registers and lg(k) reads. These drawbacks however were used to provide an atomic register which is the same as the regular register, but every read will return the most recently written value. This altered tree algorithm also requires that each binary register must be atomic unlike the original algorithm which only requires regular binary registers.

Now having finished going through all the relevant background I have observed that if the regular registers in the original tree algorithm are replaced with atomic registers the resulting structure is atomic, which improves on the previous best known result.