> Each user promises only to allocate at most one memory location at a time
> A user k can call Allocate(k) in order to get a tiny pointer p
> they can dereference by computing Dereference(k,p)
So ... every user has a unique number, and there are never more elements than users, and users are required to supply their unique number to the allocate and dereference operations ...
> We will often refer to the users (i.e., the owners of tiny pointers) as keys and to the data stored at the allocated locations pointed at by the tiny pointers as values.
> several classic problems having to do with balls and bins
Can't tell if joke, or wrong audience, or authors out of their topical comfort zone. I think the typical way to refer to such problems would be "counting problems".
"How do mathematicians get to know each other? Professional psychologists do not seem to have studied this question; I will try out an amateur theory. When two mathematicians meet and feel out each other’s knowledge of mathematics, what they are really doing is finding out what each other’s bottom line is. It might be interesting to give a precise definition of a bottom line; in the absence of a definition, we will give some typical examples."
"I will shamelessly tell you what my bottom line is. It is placing balls into boxes, or, as Florence Nightingale David put it with exquisite tact in her book Combinatorial Chance, it is the theory of distribution and occupancy." G-C Rota
https://cadadr.org/san-salvador/algebra/bottom-lines.pdf
> Each user promises only to allocate at most one memory location at a time
> A user k can call Allocate(k) in order to get a tiny pointer p
> they can dereference by computing Dereference(k,p)
So ... every user has a unique number, and there are never more elements than users, and users are required to supply their unique number to the allocate and dereference operations ...
then why not just use k as the pointer?!
I guess I need to keep reading...