[OT] Retreating from Iraq AT THE SAME TIME

[Don]

Don wrote:
> Russell Lewis wrote:
>> The solution here is just like what happens in real life at my company 
>> when a major reorg is happenning:
>>
>> * President calls, and all officers call their subordinates 
>> immediately, until the sergeants hear about it.  Then they wait.
>> * At a predetermined time (when enough time has elapsed for all 
>> sergeants to have heard the news), all sergeants call all of their 
>> platoons at the same moment.
>> * All of these calls at once overload the VOIP system, which promptly 
>> crashes.
>> * Realizing that a VOIP crash generally means that major news is 
>> coming, all privates log onto the Drudge Report and find out what is 
>> going on.
>>
>> :)
>>
>> Basic idea is that sergeants can wait arbitrarily long, so you put the 
>> onus on them to hold the info until the predetermined time.
> 
> Doesn't minimize the number of delays, though.
> Define the rank of an officer as the maximum number of levels beneath him.
> 
> Every officer of rank R (who is called at time t=0) should immediately 
> call his subordinate(s) of rank R-1 (ie, at time t=1). Then call others 
> of rank R-K at time K.

Actually, I'm assuming that 'inserting as few delays as possible' means
maximizing number of instances where an underling begins receiving his 
message from his superior as soon as the superior has received it.
But that's probably not what Andrei had in mind, since it conflicts with 
the idea of calling all subordinates at once. Instead:

If rank of the root is T:
any officer of rank R, should wait for ((rank of highest sibling)-R) 
time units before passing on the message, except of course if he has 
rank-and-file soldiers, who should be told seperately after waiting for 
(rank of highest sibling-1) time units.


> 
>>
>> Andrei Alexandrescu wrote:
>>> Let's reconsider the problem of retreating from Iraq, with a twist.
>>> Grace to new technology, teleconferencing is now possible. All direct
>>> subordinates of any officer can be called SIMULTANEOUSLY. So there is no
>>> more need for one officer to call each subordinate in sequence; he or 
>>> she will call them all at once. Cool!
>>>
>>> However, now the demands also increased. Your task, should you yadda
>>> yadda, is to devise a schedule for teleconferenced such that EVERY rank
>>> and file soldier finds the news at EXACTLY the same time. That means you
>>> must insert some delays in the system. However, you should insert as few
>>> delays as possible, and also to ensure there is minimal global delay
>>> from the moment the President picks up the phone to the moment soldiers
>>> get the news.
>>>
>>> Be warned: this is quite a different problem than the previous one in
>>> spite of the similarities. You may want to start from scratch instead of
>>> adapting an algorithm suitable for the previous problem.
>>>
>>>
>>> Good luck!
>>>
>>> Andrei