Problem adopted from P. Klein, Coding the Matrix. In 1988 I was a Computer Science graduate student. One day in November we were told that our campus was disconnecting from the Internet for a while. Our machines had been infected by a worm - a program that reproduces through the network. This was the first time such a thing had happened on the Internet. This so-called "Morris worm" made many copies of itself on each machine it infected; eventually it made an infected machine unusable The author (Robert T. Morris, Jr.) had made some effort to prevent this. The program seems to have been designed so that each worm would check whether there was another copy of the worm running on the same computer; if so one of them would terminate. However, with probability 1/7 instead of doing the check, the worm would designate itself immortal. An immortal worm would not do any future checks We will analyze what happens in such a situation, in a small network of just three computers connected in a triangle. Here is the model we will use At each timestep, each worm has a probability 1/10 of spawning a child worm on each neighboring computer. Then, if it is a mortal worm, with probability 1/7 it becomes immortal, and otherwise it dies. There is randomness in this model, so we cannot say exactly how many worms there are at step k, but we can calculate the expected number of worms. We will use a state vector mik nik m2k n2k m3k n3k in which mik represents the expected number of mortal worms on machine i at step k, and nik represents the expected number of immortal worms on machine i at step k. According to our model, any mortal worm at computer 1 is a child of a worm at computer 2 or computer 3. Therefore the expected number of mortal worms at computer 1 at step k+1 is 1/10 times the expected number of all worms at computers 2 and 3 at step k. In other words, mikt 10 3k With probability 1/7 a mortal worm becomes immortal. The previously immortal worms stay immortal. There- The equations for computers 2 and 3 are analogous Problem adopted from P. Klein, Coding the Matrix. In 1988 I was a Computer Science graduate student. One day in November we were told that our campus was disconnecting from the Internet for a while. Our machines had been infected by a worm - a program that reproduces through the network. This was the first time such a thing had happened on the Internet. This so-called "Morris worm" made many copies of itself on each machine it infected; eventually it made an infected machine unusable The author (Robert T. Morris, Jr.) had made some effort to prevent this. The program seems to have been designed so that each worm would check whether there was another copy of the worm running on the same computer; if so one of them would terminate. However, with probability 1/7 instead of doing the check, the worm would designate itself immortal. An immortal worm would not do any future checks We will analyze what happens in such a situation, in a small network of just three computers connected in a triangle. Here is the model we will use At each timestep, each worm has a probability 1/10 of spawning a child worm on each neighboring computer. Then, if it is a mortal worm, with probability 1/7 it becomes immortal, and otherwise it dies. There is randomness in this model, so we cannot say exactly how many worms there are at step k, but we can calculate the expected number of worms. We will use a state vector mik nik m2k n2k m3k n3k in which mik represents the expected number of mortal worms on machine i at step k, and nik represents the expected number of immortal worms on machine i at step k. According to our model, any mortal worm at computer 1 is a child of a worm at computer 2 or computer 3. Therefore the expected number of mortal worms at computer 1 at step k+1 is 1/10 times the expected number of all worms at computers 2 and 3 at step k. In other words, mikt 10 3k With probability 1/7 a mortal worm becomes immortal. The previously immortal worms stay immortal. There- The equations for computers 2 and 3 are analogous
