Protocols for Fault Identifcation in Partially Known Networks

Tristan Tomala

Working Papers from HAL

Abstract: We consider a group of players who perform tasks repeatedly. The players are nodes of a communication network and observe their neighbor's actions. Players have partial knowledge of the network and only know their set of neighbors. We study the existence of communication protocols that identify faults: whenever a player chooses a faulty action, the communication protocol publicly reveals the identity of the faulty player. We consider two setups. In the first one, players do not share authentication keys. We show that existence of a protocol that indentifies faults is equivalent to the 2-vertex-connectedness of the network: no single vertex deletion disconnects the graph. In the second setup, we allow players to share authentication keys. We show that existence of a distribution of the keys and of a protocol that indentifies faults is equivalent to the 2-edge-connectedness of the network: no single edge deletion disconnects the graph. We give applications to the implementation of socially optimal outcomes in repeated games.

Keywords: Networks/Graphs; Communication networks; Communications; Communication protocols; Games/group decisions; noncooperative; Repeated games.; Repeated games (search for similar items in EconPapers)
Date: 2008-06-26
References: Add references at CitEc
Citations:

Published in 2008

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:wpaper:hal-00580147

Access Statistics for this paper

More papers in Working Papers from HAL
Bibliographic data for series maintained by CCSD ().