[info] [croquet-dev] rollback [Re: basic tea-time questions]

[Eugen Leitl]

----- Forwarded message from "David P. Reed" <dpreed at reed.com> -----

From: "David P. Reed" <dpreed at reed.com>
Date: Thu, 22 Mar 2007 14:16:38 -0400
To: croquet-dev at duke.edu, Howard Stearns <hstearns at wisc.edu>
Subject: Re: [croquet-dev] rollback [Re: basic tea-time questions]
User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.8.0.10) Gecko/20070302 Fedora/1.5.0.10-1.fc6 pango-text Thunderbird/1.5.0.10 Mnenhy/0.7.4.0
Reply-To: croquet-dev at duke.edu, "David P. Reed" <dpreed at reed.com>

The solution Andreas was referring to as being inefficient was rollback 
at the object level.   What is efficient enough is of course debatable - 
partly depending on the frequency of rollback needed and the cost 
overhead incurred when running forward.  Andreas and I have a dispute as 
to what is "efficient enough", while we share a view that modifying the 
Smalltalk VM in radical and complex ways is something that we should 
undertake with great care and as a last resort (especially since a new 
VM implementation paradigm - Coke - is in process that would make a 
better place to try out a rollback scheme).

Letting multiple flowers bloom at the bottom layer of the system is 
interesting for research exploration, but the short-term plan for 
Croquet has been focused on achieving deployment at scale, not 
continuous low-level re-design and bug introduction, with no progress on 
UI or collaboration experience.  So I agree with the current focus of 
efforts on building a useful, scalable system, with improvements to be  
done later.  To preserve the opportunity to drop the "router", just 
don't build in unnecessary dependencies on having a "router" (in other 
words, adopt the core "end-to-end argument" which says if there is any 
way to avoid adding function to central resources like the router, do 
so, even if it seems cheaper to toss it into the router*).

* Those of you who think the "end-to-end argument" is a four letter word 
(the number who respond viciously to my mentioning it  as a good thing 
increases daily) can ignore the last sentence. Or not - I' like arguing. :-)

Howard Stearns wrote:
>All is well. Fortunately, other issues seem to dominate at the current 
>state of development (in my opinion). So it isn't really a problem to 
>be dependent on clock ticks from the router in order to move animation 
>along.  I don't have any opinion on when it will matter.
>
>But it's still interesting to look at rollback.
>
>Brie uses dependency-directed backtracking to provide an efficient 
>means of rollback. The motivation was not optimistic execution, though 
>-- it was to allow safe composition of separately written behaviors in 
>an unpredictable event-driven environment.  But a nice result is that 
>arbitrary events can be undone out-of-order.
>
>I would like to exploit this to provide efficient object-oriented 
>"undo." [User selects any arbitrary combination of one or more objects 
>to obtain a merged timeline of events. User can slide back and forth 
>to any point on any *branch* of the timeline, with all dependencies 
>unwound (even in objects not selected).]
>
>Note that there's no need to limit things to "reversible" behaviors.
>
>Given this, I think optimistic execution becomes pretty easy, no?
>
>Of course, this only works where everything that effects the semantics 
>of simulation (e.g., not including rendering) is handled as a 
>Briehavior, and that's not really acceptable at the basic core Croquet 
>infrastructure level.
>
>Alas, I'm not convinced that there is absolutely no way to create a 
>history-dependent undo state. That's not a problem for replicated 
>user-initiated undoing -- the worst that can happen is that all users 
>get an unexpected result. But it's fatal for non-replicated internal 
>corrections for late-arriving past messages.
>
>
>Andreas Raab wrote:
>>...
>>Unfortunately, although we discussed this problem in excruciating 
>>detail, we were never able to find an efficient solution to the 
>>rollback problem (at least not in our current implementation; perhaps 
>>this will get easier with transactional memory). ...

----- End forwarded message -----
-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820            http://www.ativel.com
8B29F6BE: 099D 78BA 2FD3 B014 B08A  7779 75B0 2443 8B29 F6BE