All right, taking Meni Rosenfeld's considerations into account, how is this for a formal proposal for a constant-share pool:

1. When the round ends, the pool will use the block reward (minus fee) to pay equally for all of the latest "difficulty/2" shares
The mean number of shares in a round is always equal to the difficulty, regardless of pool size, since each share is a solution of difficulty 1, and each share has 1/d probability of solving the block. In comparison to share-based pools, on average, you will be paid for exactly half of the shares you submit to the pool (twice as much, of course), and the reward will be constant if your hashing power as a fraction of the pool's total hashing power is constant.

2. If there are less than d/2 shares in the round, the pool with use the rollover reward to pay for the latest unpaid shares in the previous round(s)
The rollover eliminates the risk of pool hopping, since there is never an advantage or disadvantage to mine very early or very late in a round.

3. The pool will cache the last 10d shares, in case there is a very lucky streak of very short rounds
There needs to be a cache of sufficient size for the rollover to be effective. With a cache of size 10d and payout slices of size d/2, there is a (very roughly) 1/2^20 (one in a million) chance that the cache will soon be exhausted.

4. If there are lucky blocks at the very start of the pool's lifetime, the pool will hold on to the rollover to distribute to the miners in the unlikely/inevitable event that the pool is shut down permanently
This is a mostly trivial point and you have to trust the pool operator to carry through with this promise, but this terminal fund simultaneously resolves two problems:
a) The end-of-life problem: if a pool is shut down, the round never ends and the miners who contributed to it are left holding an empty bag. But with the terminal fund, the miners can continue to mine with security, even if there is uncertainty of whether the pool is about to close.
b) The initial pool problem - what to do with the rollover at the beginning of a pool's lifetime. The fund is a clever way to short circuit the end of the pool's lifetime to its beginning, tying up all loose ends. The other two alternatives are to distribute the bonus to the miners - the early adopter advantage - or for the operator to keep it.

5. When difficulty changes, the reward interval follows; the rollovers will occur as normal, except that older shares have a higher weight equal to "new difficulty/old difficulty"
The reward interval is fixed to difficulty/2 to maintain constant variance, regardless of pool or network size. This necessitates using correct transitions during difficulty changes. I believe the above is the correct way to transition. Shares after difficulty change are worth proportionally less than shares before change, because they are instantaneously less likely to solve the block. People complain why PPS dropped so much so quickly - it all has to be tied directly into the difficulty. This method also accurately handles difficulty decreases.

Finally, here is my reference implementation of the constant-share pool, written in perl. The first part is the actual algorithm demonstrating the details of the rollover and the difficulty changes. The second part is a simulation of a typical pool that uses constant-share payments. Run the program to see the pool operate. Notice the memory usage: the stack takes up about ~100 bytes per share, or 400MB for a full cache at current 400k difficulty - manageable even in the implementation's current state. Of course, perl is memory-inefficient, and in a production implementation, the stack should only take up 4 bytes per share (a single integer user id), be stored in a database, and be periodically saved to disk. As difficulty increases, the stack would grow, but as pools decide to increase work difficulties higher than 1 to relieve pool load, fewer shares will need to be cached for payout calculations.

You are right. I finally found an integrator that works, and between 0% and 14% round time, I get 19.80% of my total reward in slush's pool, compared to 13.06% of total reward while mining solo - a 52% premium, but only 6.7% over all time. Of course, if the network hashing power were divided equally among 6 score-based pools, then instead of only 14% of the time, I could mine at a premium 84% of the time (or however much it adds up to), for a 40% (or however much) total premium. However, since the majority of the network hashing power is currently in share-based pools, that is not even necessary.

That is all correct. Sometimes I forget that the real world is discrete. The utility of the very first share in a round is not infinite but very much finite (x13 seems reasonable), since shares are not infinitely divisible and integrable. Also I agree that the maximum theoretical efficiency of multi-pool hopping is limited by the fact that on average no more than 6 blocks can be found per hour.

Keeping a stack of several million of the latest shares is not particularly memory-intensive. Even less-so if the oldest shares are offloaded to disk, before sometime later all record of them is finally deleted (very old shares are exponentially-unlikely to be needed for payout). Also, it is not pay-per-share and carries no risk for the operator, since all payouts come from each solved block and not out-of-pocket.

Not really - the pool that has just found a block is always the best, though it might be better to switch back to a slower pool at some later time. There is no penalty. The utility of each submitted share is independent of any other share (unless you are a dominant contributor to the pool).

For difficulty d and pool hashrate R, the probability that the round will end in exactly time t is:
$ p(t) = \frac{R}{2^{32}d} e^{\frac{-tR}{2^{32}d}} $
If we express time in units of mean lifetime $ Tm = \frac{2^{32}d}{R} = 1 $, this simplifies to:
$ p(t) = e^{-t} $
The expected reward for a single hash submitted T time into a round is the integral over all possible total round times of this probability divided by the total number of pool hashes in the round:
$ E(T) = \int_T^\infty \frac{e^{-(t-T)}}{Rt} dt = \frac{e^T}{R} \int_T^\infty \frac{e^{-t}}{t} dt = -\frac{e^T}{R} Ei(-T) $
Your solo expected reward is always 1/(d*2^32), so your pool/solo reward ratio, or efficiency, is (using mean lifetime units, where d*2^32/R = 1):
$ r(T) = -e^T Ei(-T) $
http://www.wolframalpha.com/input/?i=+-e^T+Ei%28-T%29+%3D+1
The efficiency drops below 100% at exactly 0.434818... mean lifetimes into a round. Efficiency is pretty high early on though. When mining solo, you earn $ \int_0^{0.4348} e^{-T} dT = 35.26\% $ of all your rewards during the 0 to 43.58% mean lifetime round interval, but in a pool you earn $ \int_0^{0.4348} -Ei(-T) dT = 63.41\% $ of your total rewards in that interval - a 79.83% bonus. Across all time, your average reward is highest if you hop at 43% point:
$ \int_0^{0.4348} -Ei(-T) dT + \int_{0.4348}^\infty e^{-T} dT = 1.2814 $ - a 28% bonus. Multi-pool hopping works even better, since you always pick the pool with the highest current expected reward, which is the pool with the smallest round time/mean round time ratio. As I said, I only rotate between four pools, and not always is there a pool with round time below 43%, so I average about 70% extra efficiency over entire time, but the bonus can be pushed above 100% using many more pools.

It is somewhat of a philosophical question of whether 1% here and there really makes a difference, and whether you should actually care whether it is 43% or 43.5% or whatever, but this is what the math says. Again, since hopping only takes a second, you take no time penalty from doing so anytime you wish.

For Slush: the score-based method, as implemented, is better, but not perfect. If a share at time t into a round gets a score $ s = u + e^{t/v} $ where v, the decay constant, is 300 seconds and u is 1 (it doesn't make much difference actually), the total score of a round of length t is:
$ s(t) = \int_0^t R (u+e^{t/v}) dt = R (ut + v(e^{t/v} - 1)) $
And the expected reward ratio for a share submitted T time into a round is (using the reduction d*2^32/R =1 ):
$ r(T) = \int_T^\infty \frac {e^{-(t-T)}(u + e^{T/v})} {ut + v(e^{t/v}-1)} dt $
I don't have a plot of this curve unfortunately, only some numerical approximations. For 542GHash/s, Tm is 3446 seconds, so decay constant v is 0.0871Tm. and assuming u=1:
r(0.01)=261.40%
r(0.10)=109.87%
r(0.14)=99.25%
r(0.43)=91.15%
r(1.00)=91.98%
r(10.00)=91.99%
The important point to see here is that the expected reward ratio is not 100%, as claimed, but rather drops below 100% at 14% round mean lifetime, and hovers around 92% from there on. Averaged over all time, I can make 10%-20% extra by only mining in slush's pool in the first 14% of a round.

Again, I recommend pool operators to familiarize themselves with the math that makes pool-hopping efficient, and implement an algorithm, like Meni Rosenfeld's geometric score, that is provably neutral. I also request people to review my constant-time proposal, since I believe it would be easier to implement/understand than exponential scores (linked lists instead of logarithm math).

That's right, you jump to the shares-based pool with the presently lowest round_time/mean_round_time fraction, or score-based pool if none are below 43% fraction. The switching takes only a second and is not a problem. I use a script to query the pools periodically/whenever bitcoind reports a new block and redirect the miners as necessary. This also simultaneously solves the unplanned pool downtime issue. Interestingly, bitcoind always reports new blocks at the same time as pools pushing new longpoll work, or no more than 10 seconds apart. Since the daemon and the miners use entirely different connections, that means transactions/block solutions are being propagated across the entire bitcoin network within 10 seconds or less on average.

@Meni Rosenfeld
I mostly lurk. So
is an accurate description.

@Meni Rosenfeld

Thank you, yours was the algorithm I was referring to! That is the single most insightful and precise mathematical analysis on these forums, and I did not mean to bash it. I guess I am merely dissatisfied with score-based methods in general, because they make it less clear intuitively how much each share is worth. There is also the problem with large exponential numbers that need to be rescaled for long rounds (or stored as logarithms). Ultimately though, any fair method is better than naive method.

@slush
The decay constant of 300 seconds means that the shares of the past 5 minutes are worth 2.7 times as much as all the previous shares combined, so you are not burdened with others' old shares when mining in a long round. But there is a high variance (you aren't getting anything unless you happen to mine in the last 5 minutes of a round) and you still have the deadweight of the last 5 minutes' worth of shares, such that after about 1/2 mean round time, you are mining at only 90% efficiency (efficiency doesn't keep going down below 90% though, unlike with standard shares). Up to 15% mean time, efficiency is greater than 100%, and it is greater than 200% in the first couple minutes, so I get 20% extra on average (across entire round time) by hopping. Using shorter decay constant would decrease the gain, but would increase the variance even more.

Look, I'll confess (anonymously), I pool hop and it works.

Pool hopping is not cheating - it is optimizing. It is the responsibility of pool operators to implement algorithms that are fair. I'd think of all people, cypherpunks like bitcoin miners would be the first ones to recognize this fact. If you place all your trust into math, don't suddenly complain about fairness if your math turns out to not be good enough.

Hopping away from a single pool (at 43% of mean round time) earns 30% more. Hopping between a couple pools (I have 4 currently automated) earns me 70% more. If you'd automate a dozen pools, you could earn more than 100% extra.

Slush's pool is not secure because he messed up his algorithm. I earn 20% more on his pool. Deepbit pool is not secure, because they got a large market share. If no other pool solved the block (which I know automatically), it was most likely deepbit, even if their statistics are delayed by an hour.

Pool hopping is not too common. I've analyzed the statistics of the pools I use, and less than 5% of users pool hop, so "unsofisticated" pool miners only loose 2-5% of income. After publishing this post, I expect hopping to become more common.

What I want to happen is for pool miners to implement mathematically-fair payment algorithms. This is the solution best for the community in the end, but not manually enforcing no-hopping rules or withholding information. There is a complicated score-based algorithm published somewhere on this forum (not slush's algorithm) that seems secure, though I didn't check it in too much detail. There is a much simpler fair algorithm though, which I want you to confirm: pay for all shares submitted in the last 1 hour of a round. If a block is found sooner than 1 hour into a round, then rollover the extra time and pay for the unpaid shares of the previous round, or the previous round before that (if the previous round was shorter than an hour as well), and so on. This way, each share has equal expected utility regardless of when it is submitted - early on or late in a round. Late shares in long rounds are subsidized by early shares in short rounds. You can use any time interval shorter than the mean round time. I'd recommend 1/4 of the mean time, e.g. 1 hour for a 130GHash/s pool.