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.

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

Gregor Richards Wrote:

> John Reimer wrote:
> > Hello Gregor,
> > 
> >> You want to destroy all life on Earth. However, you don't want people panicking as this could alter the result, so you want all humans to die at the same instant. To do this, you're creating nano-robots. A single nano-robot cannot control a persons mind: Seven are required (three in each half of the brain and one in the brain stem). Nano-robots can harvest material from their host to build new nano-robots, but the host will die after approximately twenty nano-robots-worth of material has been harvested (they require particular rare particles that can only be harvested from the heart and lungs). Nano-robots may communicate with one-another via broadcast, but the range is limited to 1 mile. Nano-robots do not have unique identification globally, but do have unique identification within a body (that is, nano-robots in the same body can distinguish each other, but broadcast messages from a nano-robot in one human cannot implicitly be distinguished from broadcasts from another). These broadcasts travel at the speed of light (seeing as that they are light). Nano-robots harvest energy from their host, and as such can survive indefinitely. A nano-robot in a dead host survives long enough that this variable is not relevant for this problem.
> >>
> >> Robots can only be spread by direct physical contact from an infected host to an uninfected one, and the process of transferring one nano-robot destroys two nano-robots (that is, the infected host loses three robots in the process but the new host only gains one).
> >>
> >> Devise an algorithm for these nano-robots that will destroy all human life on Earth in a minimum amount of time, but with which all humans will be destroyed within five minutes of each other. That is, minimize the time from deploying the first nano-robot to the initial human life being exterminated, and minimize the time from the initial human life being exterminated to all human life being exterminated. You may assume a maximum of twelve degrees of separation between average industrialized people and that even the most remote tribe is connected by at least one human to the industrialized world.
> >>
> >> Bonus: How would you change this algorithm if you wanted to destroy all animal life? All life? How would you change it if astronauts were considered?
> >>
> >> - Gregor Richards
> >>
> > 
> > 
> > Ok, Gregor.  I'll bite.  What's your fascination with this problem?  Are you trying to make a point about something?
> > 
> > If "yes", you may as well be direct about it.  If "no", then why the
> > thread hijacking?  Come on... help me out... I'm a little slow
> > sometimes. :)
> > -JJR
> > 
> > 
> 
> Thread hijacking? Seriously? This isn't a forum, there are totally disconnected subthreads within any thread.
> 
> This is what we call a "joke".

no pal. this is what /you/ call a "joke". wasn't funny the first time. second time looks stupid.

> On the one hand it's a parody of the always-annoying real-life-algorithm thread, on the other hand it's a parody of the needlessly-loaded choice of settings for the oh-didn't-I-mention-it's-always-annoying real-life-algorithm. This problem could be formalized as a simple tree-based message-passing communication problem, but instead we've gone political. Well, so long as war is involved, let's step it up and destroy everything. Yeeee haw.

so ur the sharpest tool in the shed eh. why don't you send in your solution. tree-based message-passing sounds like bullshit you'd say when you have no idea. this is a classic signal propagation problem in circuits, i solved it all the time when i was working on async vlsi. and tree-based message-passing has nothing to do with it. the man made it a story. that /is/ funny. if it annoys u piss off.

Nick Sabalausky wrote:
> "Andrei Alexandrescu" <SeeWebsiteForEmail@erdani.org> wrote in message news:gd6ifg$8g3$3@digitalmars.com...
>> 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.
>>
> 
> Can a subordinate initiate a call to a superior? 

No, but the hierarchy is known in advance.

Andrei

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.

> 
> 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

superdan wrote:
> Gregor Richards Wrote:
> 
>> This is what we call a "joke".
> 
> no pal. this is what /you/ call a "joke". wasn't funny the first time. second time looks stupid.

This "we" is what we call the singular "we". So's that one. And with the insults I'm crying on the inside. Actually, I'm laughing, but y'know how sometimes laughing and crying sort of sound similar? Yeah, that's the situation.

> 
>> On the one hand it's a parody of the always-annoying real-life-algorithm thread, on the other hand it's a parody of the needlessly-loaded choice of settings for the oh-didn't-I-mention-it's-always-annoying real-life-algorithm. This problem could be formalized as a simple tree-based message-passing communication problem, but instead we've gone political. Well, so long as war is involved, let's step it up and destroy everything. Yeeee haw.
> 
> so ur the sharpest tool in the shed eh. why don't you send in your solution. tree-based message-passing sounds like bullshit you'd say when you have no idea. this is a classic signal propagation problem in circuits, i solved it all the time when i was working on async vlsi. and tree-based message-passing has nothing to do with it. the man made it a story. that /is/ funny. if it annoys u piss off.

Yes, my joke is my CLAIM OF DOMINANCE. Anyone who uses humor is claiming that they are the greatest of all human beings. HOW DARE YOU SUGGEST OTHERWISE YOU HUMORLESS PIG.

It amuses me that my realization of the problem is, to you, a statement that I must be utterly ignorant of everything, but you immediately proceed to make a different realization of the problem. And yet, scanning over the responses, you too haven't posted an actual algorithm. Hey wait, it amuses me, which must mean you were making a joke, which means you're CLAIMING DOMINANCE! Damn!

Why is it a tree-based message-passing problem? Because this is software, dingus, not hardware. You have a TREE of actors (or threads, or processes as you prefer. I'll go with actors because they're usually associated with message-passing concurrency). Every actor needs to send MESSAGES to all its subordinates. Why, lo and behold, it's a tree-based message-passing problem!

Yeesh.

 - Gregor Richards

John Reimer wrote:
> Hello Gregor,
> 
> 
>> This is what we call a "joke". 
> 
> Yet... if it is just a "joke", that implies you are not serious... and yet I do think your parody is meant to make a statement beyond just a "joke". Sorry, I think it's fair to hold you accountable for your "jokes". :)  In short, it's not a joke then.
> 
> Your parody and strong statement of annoyance appear to have been meant to "educate" the community.
> -JJR
> 
> 

You think that jokes can't carry messages beyond their humor? That they have to be entirely without serious content? You must live a profoundly humorless life, as the vast, VAST majority of jokes serve as vessels for some sort of message.

 - Gregor Richards

Hello Gregor,

> John Reimer wrote:
> 
>> Hello Gregor,
>> 
>>> This is what we call a "joke".
>>> 
>> Yet... if it is just a "joke", that implies you are not serious...
>> and yet I do think your parody is meant to make a statement beyond
>> just a "joke". Sorry, I think it's fair to hold you accountable for
>> your "jokes". :)  In short, it's not a joke then.
>> 
>> Your parody and strong statement of annoyance appear to have been
>> meant
>> to "educate" the community.
>> -JJR
> You think that jokes can't carry messages beyond their humor? That
> they have to be entirely without serious content? You must live a
> profoundly humorless life, as the vast, VAST majority of jokes serve
> as vessels for some sort of message.
> 
> - Gregor Richards
> 


Come now, Gregor, what's with the wild conjectures?  Or is this just a hyperbolic joke in which I'm once again missing the message?  We're on a roll here! :-)

Nope, I just thought that saying it was a "joke" was like equivocating somewhat on your purpose for posting, kind of like an attempt to lighten a situation when you suddently see everyone has got deadly serious.  You may "snort" at that suggestion, but you can't avoid perception... well ... you can... but it may come back to bite you. :-)

The only real difficulty I have in conversing with you, Gregor, is the mental exercise involved in order to guess whether you are serious or not.  If everything is a "joke" or "parody" (with or without a message) for you, which it may not be to others, then communication breaks down.  That's all I'm saying.  To you this may indicate my level of intelligence by my inability to comprehend; but hey, you got know how to speak to the little guys too (or maybe, you just don't want to). 

Actually, I feel a little sheepish here.  Everytime I get back into this newsgroup, no matter how hard I try, I get pulled into wranglings like this (my fault for asking, I suppose): it's kind of my nature to want mend these sort of issues, and sometimes I mess up big time by getting invovled.  I guess I have to learn to leave well enough alone sometimes in a group where everyone has a say.  

No doubt we all have our peculiarities.  I'll stop hounding you on this, Gregor, but I sure wish you would go against your nature sometimes, and cut the scathing sarcasm.  You do come across -- perhaps in a parallel vein as superdan minus the foul mouth -- as if you exist at the center of everything. On the other hand, over the last couple of years, I've been able to appreciate other aspects of your character despite the existance of this one.  No, not trying to placate you with a final "nice" word... okay... maybe a little. Otherwise, I'm just trying (lamely perhaps) to say that it's "not all bad" and wish you could do better.

-JJR

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