Sort of except (at least by my understanding, feel free to correct me if I'm wrong) a 'typical' memory bound proof-of-work would be bandwidth/latency limited, with little consideration for volume of memory. I would prefer the AMOUNT of memory to be the limiting metric rather than (primarily) that memory's speed. I feel that this would allow the network to grow more smoothly as it is entirely possible to acquire additional memory but not really feasible to speed memory up beyond a certain maximum. I feel that steady growth of the network is necessary to maintain security.
Linear scaling of mining performance with RAM - It would be important that mining performance scale linearly (rather than exponentially or logarithmically) with the amount of available RAM (and possibly speed of said RAM).
I don't think that's realistic. You'll probably need to scale computing power along with the memory. Something like
"1 memory bank + 1 virtual core = 1 vote"
If one virtual core is waiting on a random access to a memory bank (incurring row switching latency), then other memory banks can still be serving requests from other cores.
I agree that it would probably not be possible to have zero computational overhead, but I think it would be best if that overhead was as minimal as possible. Ideally, an ordinary desktop CPU could fully utilize a very large memory bank for mining purposes. This may not be possible, but I think it would be best if it could be achieved (primarily for reduced power usage).
I would argue for the following desirable properties of a memory bound PoW:
a target memory footprint that exceeds a single memory chip
Ideally, I think that mining performance should scale with the amount of memory available. I think you are imagining a scenario where a mining algorithm uses a large but finite amount of memory, and access to sufficient memory would allow mining. I am imagining instead an algorithm that uses all available memory, and performance scales with the size of that memory space. This might be achievable by running as many instances of a mining algorithm as will fit in available memory, where each instance uses minimal CPU time but a large (but finite) amount of memory, and hashes at a fixed rate (not sure how that fixed rate could be set).
a pattern of necessarily random memory accesses
minimal computation per random memory access
Agreed and agreed, as much memory as possible should be accessed in each computation, and memory access should be random to ensure that the miner keeps an entire data set in memory (rather than loading items in and out as necessary). There needs to be some advantage, however, to having a very large data set in memory compared to a small one.
no feasible trade-off of memory for time
I think what you mean is that you shouldn't be able to simulate a very large amount of memory by paging data in and out of physical memory. If so, I entirely agree.
And of course instant memory less verification...
Not quite sure what you mean by this, could you explain in a bit more detail?