Today is National Puzzle Day, the perfect day to do a little brain teaser. Roke people are curious and unashamedly technical, and we love working closely with our customers to solve their most complex problems. We invited one of our engineers, Mark, to breakdown his favourite puzzle, which was actually developed as part of a research project we conducted.
Alice, the sender, is trying to send a message to Bob, the receiver. To do that there needs to be an active path in the network between them. Unfortunately the links in the network are not reliable: a link will be active at any given time with probability p. Messages are assumed to be sent instantaneously, by any available path, with no loops. Nelly, the network engineer, has time to set up eight links and offers Alice a choice of two network configurations, A or B (left). Which one should Alice choose to give her the best chance of being able to communicate with Bob?
It depends on the probability, p! When reliability is good, network A is the best. When the links are less reliable, Alice would be better choosing network B.
Network A keeps working if any single link is broken, but is more likely to fail if two (or more) links break. Network B has more possible paths (four) so can cope with more double link breaks, even though all the paths share a common link.
Mathematically, network A allows Alice and Bob to communicate with probability p3 + p5 – p8 (it works if either the path of length 3 or length 5 work). Network B is more complex and works with probability p3 + 3p5 – 2p6 – 3p7 + 2p8. From this we can work out that network A is only more reliable if p>√2⁄3, or where links have about an 82% chance of working. Otherwise, network B is more reliable.
This result comes from research that Roke conducted as part of the International Technology Alliance for Network and Information Sciences. It's a theoretical result with practical application: when deciding whether or where to add a link to a radio network, we can use results like this to understand how different combinations of links affect reliability.
The paper from which this example is taken can be downloaded below.