How can we generate a permutation of the numbers 1 through n such that, given the history so far, it is hard to guess the next element? The twist is that the permutation generator (the "Dealer") has limited memory, while the "Guesser" has unlimited memory. With unbounded memory (or even just n bits), the Dealer can generate a truly random permutation, for which the expected number of correct guesses is ln n.Our main results establish tight bounds for the relationship between the guessing probability and the memory m required to generate the permutation. We suggest a method for an m-bit Dealer that operates in constant time per turn and ensures that any Guesser can correctly guess only O(n/m + log m) cards in expectation. The method is fully transparent, requiring no hidden information from the Dealer (i.e., it is "open book" or "whitebox").We further show that this bound is essentially optimal, even if the Dealer is allowed to use secret memory. Specifically, for any m-bit Dealer, there is a (computationally powerful) Guesser that achieves Ω(n/m + log m) correct guesses in expectation. We point out that the assumption that the Guesser is computationally powerful is necessary: under cryptographic assumptions, there exists a low-memory Dealer that can fool any computationally bounded Guesser.Finally, we present an O(n) bit memory Dealer that generates perfectly random permutations and operates in constant time per turn.

A card guessing game is played between two players, Guesser and Dealer. At the beginning of the game, the Dealer holds a deck of $n$ cards (labeled $1, ..., n$). For $n$ turns, the Dealer draws a card from the deck, the Guesser guesses which card was drawn, and then the card is discarded from the deck. The Guesser receives a point for each correctly guessed card. With perfect memory, a Guesser can keep track of all cards that were played so far and pick at random a card that has not appeared so far, yielding in expectation $\ln n$ correct guesses. With no memory, the best a Guesser can do will result in a single guess in expectation. We consider the case of a memory bounded Guesser that has $m < n$ memory bits. We show that the performance of such a memory bounded Guesser depends much on the behavior of the Dealer. In more detail, we show that there is a gap between the static case, where the Dealer draws cards from a properly shuffled deck or a prearranged one, and the adaptive case, where the Dealer draws cards thoughtfully, in an adversarial manner. Specifically: 1. We show a Guesser with $O(\log^2 n)$ memory bits that scores a near optimal result against any static Dealer. 2. We show that no Guesser with $m$ bits of memory can score better than $O(\sqrt{m})$ correct guesses, thus, no Guesser can score better than $\min \{\sqrt{m}, \ln n\}$, i.e., the above Guesser is optimal. 3. We show an efficient adaptive Dealer against which no Guesser with $m$ memory bits can make more than $\ln m + 2 \ln \log n + O(1)$ correct guesses in expectation. These results are (almost) tight, and we prove them using compression arguments that harness the guessing strategy for encoding.

This paper presents the architecture for a self-stabilizing hypervisor able to recover itself in the presence of Byzantine faults regardless of the state it is currently in. Our architecture is applicable to wide variety of underlying hardware and software and does not require augmenting computers with special hardware. The actions representing defense and recovery strategies can be specified by a user. We describe our architecture in OS-independent terms, thus making it applicable to various virtualization infrastructures. We also provide a prototype extending the Linux-based hypervisor KVM with the self-stabilizing functionality. These features allow augmenting KVM with robustness functionality in the coming stages and moving to cloud management system architectures such as OpenStack to support more industrial scenarios.