The Anthropic Side Channel (was: How would shallow generators compose with lambda?)

[Mark S. Miller]

On Thu, May 14, 2009 at 3:42 PM, Brendan Eich <brendan at mozilla.com> wrote:
> On May 14, 2009, at 2:50 PM, Mark S. Miller wrote:
>
>>> If so, did you have a different way of reasoning about the reasons today
>>> why
>>> finally might not run that I mentioned (iloop detection or other hard
>>> stop)?
>>
>> Those hard stops kill all further activity within that event loop.
>> Once a universe has been destroyed, no further bad things can happen
>> in that universe.
>
> There's always the next universe (new event starts another control flow).
> Life goes on, in the JS serial multiverse, and those finally clauses failed
> to run even though control abruptly left the lambda under the hypothesis.


I am assuming that a hard stop destroying an event loop also destroys
(at least makes inaccessible) all objects that were able to execute
within that event loop. For example, if the event loop corresponds to
a page, a hard stop might force a reload of that page, allocating a
disjoint fresh set of objects. If objects that were able to execute
within a suddenly terminated event loop were still reachable by later
events, then we'd have all the consistency problems explained at
<http://java.sun.com/javase/6/docs/technotes/guides/concurrency/threadPrimitiveDeprecation.html>.
The invariant hazards explained there may be more vivid in the face of
multithreading, but they do not depend on multithreading.




>> Infinite loops don't kill their universe, so this case is similar but
>> different. As the halting problem teaches us, an infinite loop is
>> generally indistinguishable from a loop that hasn't terminated yet.
>> Since control flow has not yet escaped the loop, it hasn't yet
>> bypassed the finally, and so no invariants have yet been violated.
>
> True enough, but see above.

While the iloop is running, the event loop is busy, so no further
events can enter.


> This isn't entirely academic, since information leaks include termination
> channels.

I do not expect to be able to plug such information leakage channels,
and was not trying to. But again, this doesn't endanger any object
invariants.

A similar, but (to me at least) more surprising information leakage
channel is something I've called "The Anthropic Side Channel":

Within universe U, under normal conditions, A will run B and then A
will run C. B and C have no access to each other, and A invokes each
of them careful to not let info flow from B to C. However, this
universe is built on fail stop foundations. No agent can cause the
universe to diverge from its laws of physics, but any agent may induce
a condition such that the universe cannot proceed without diverging.
Under such conditions, the universe halts so that there's no
detectable violation.

Three concrete examples:

* Virtually all formal semantics for memory safe languages can only be
implemented faithfully given an infinite memory. Of course, infinite
memory is a bit too expensive, so instead hi integrity languages (e.g.
Erlang) halt and terminate the process in question. If B allocates too
much memory, this universe is destroyed before C can execute.

* In a sequential imperative system such as JavaScript, if B goes into
an infinite loop, C is never executed.

* In transactional systems, often there is an ambient abort()
primitive available, such that any participant in a transaction can
cause that transaction as a whole to abort, abandoning all state
changes that had happened during the transaction. If B aborts, C is
never executed. More to the point, nothing that C would have done gets
committed.

So, the anthropic side channel enables B to communicate what Brendan
might call a half a bit of information to C. If B does

  if (x) { abort() }

then, if C gets to execute at all, it knows !x. If x is true, then C
never does get to know it, which is why less than a bit has been
communicated.

-- 
    Cheers,
    --MarkM