

![0_image_0.png](0_image_0.png)

representing the status of machine i, takes values in {Good, Faulty, Dead}**; if its value is**
Faulty, then processes have a smaller probability of terminating and if its value is **Dead**,
then any running process is lost and Loadi becomes Idle. The status of machine i can become Faulty and eventually Dead at random; however, if machine i **receives a packet from**
a dead machine, then the probability that Statusi becomes Faulty and then Dead **increases.**
The Selectori variable represents this communication by selecting one of **the neighbors of** i uniformly at random at every time step. The SysAdmin can select at most one computer to reboot at every time step. If computer i is rebooted, then its status becomes **Good**
with probability 1, but any running process is lost, i.e., the Loadi variable becomes **Idle**.

Thus, in this problem, the SysAdmin must balance several conflicting goals: rebooting a machine kills processes, but not rebooting a machine may cause cascading faults in network.

Furthermore, the SysAdmin can only choose one machine to reboot, which imposes the additional tradeoff of selecting only one of the (potentially many) faulty or dead machines in the network to reboot.

We experimented with two types of basis functions: "single+" includes indicators over all of the joint assignments of Loadi, Statusi and Selectori**, and "pair" which, in addition,** includes a set of indicators over Statusi, Statusj , and Selectori = j**, for each neighbor** j of machine i in the network. The discount factor was γ = 0.**95. The variable elimination**
order eliminated all of the Loadi **variables first, and then followed the same patterns as in**
the simple SysAdmin problem, eliminating first Statusi and then Selectori **when machine** i is eliminated.

Figure 17 compares the running times for the table-based implementation to the ones for the rule-based representation for three topologies: "Star," "Ring," and "Reverse star." The "Reverse star" topology reverses the direction of the influences in the "Star": rather than the central machine influencing all machines in the topology, all machines influence the central one. These three topologies demonstrate three different levels of CSI: In the