Moving in a network under random failures: A complexity analysis

详细信息	查看全文 | 推荐本文 |

• 作者：Dominik Klein^b ; ^{dominik.klein@jaist.ac.jp} ; Frank G. Radmacher^a ; ^{radmacher@automata.rwth-aachen.de} ; Wolfgang Thomas^a ; ^{thomas@automata.rwth-aachen.de}
• 关键词：Game theory ; Sabotage games ; Probabilistic systems ; Fault-tolerant systems
• 刊名：Science of Computer Programming
• 出版年：2012
• 期刊代码：108_01676423
• 类别：cp
• 出版时间：1 July, 2012
• 卷：77
• 期：7-8
• 页码：940-954
• 文件大小：381 K

摘要

We analyze a model of fault-tolerant systems in a probabilistic setting, exemplified by a simple routing problem in networks. We introduce a randomized variant of a model called the 鈥渟abotage game鈥? where an agent, called 鈥淩unner鈥? and a probabilistic adversary, 鈥淣ature鈥? act in alternation. Runner generates a path from a given start vertex of the network, traversing one edge in each move, while after each move of Runner, Nature deletes some edge of the current network (each edge with the same probability). Runner wins if the generated finite path satisfies a 鈥渨inning condition鈥? namely that a vertex of some predefined target set is reached, or-more generally-that the generated path satisfies a given formula of the temporal logic LTL. We determine the complexity of these games by showing that for any probability and , the following problem is PSpace-complete: Given a network, a start vertex , and a set of target vertices (resp.聽an LTL formula ), and also a probability , is there a strategy for Runner to reach (resp.聽to satisfy ) with a probability ? This PSpace-completeness establishes the same complexity as was known for the non-randomized sabotage games (by the work of L枚ding and Rohde), and it sharpens the PSpace-completeness of Papadimitriou鈥檚 鈥渄ynamic graph reliability鈥?(where probabilities of edge failures may depend on both the edges and positions of Runner). Thus, the 鈥渃oarse鈥?randomized setting, even with uniform distributions, gives no advantage in terms of complexity over the non-randomized case.