Network reliability

Over on my other blog I’ve started writing about an interesting but apparently nontrivial problem, which some readers of this blog may find interesting as well. Suppose you have a network of computers with some one-directional wires between them. Each wire is labelled with the probability that a message sent along the wire will successfully reach the computer on the other end; assume that each message sent along a wire succeeds or fails independently of any other messages sent on the same wire. Every time a computer successfully receives a message along an incoming wire, it immediately resends a copy of the message along each outgoing wire. The question is: given some particular network, if we start a message at a particular computer s, what is the probability that at least one copy of the message will reach a given target computer t?

As a simple example, can you figure out the probability that a message starting at s in the diagram below will successfully reach t?

The solution can be found on my other blog — more to come!


About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in links, probability and tagged , , , . Bookmark the permalink.

2 Responses to Network reliability

  1. Christian says:

    This seems to be related to Baysian Networks / Graphical Models, which are used to propagate evidence about some random variables throughout a network (graph) where edges encode statistical dependencies…

    • Brent says:

      Yes, someone made a similar comment over on my other blog! I learned a tiny bit about Bayesian networks a long time ago in a class in grad school, but had forgotten about them. It definitely seems related, though I don’t yet understand any of the details well enough to see what light that might shed on the problem.

Comments are closed.