iPath: Intelligent and optimal path selection for Byzantine fault tolerant communication

This paper considers reliable communication in presence of Byzantine faulty nodes, using multiple node-disjoint routes. To tolerate f Byzantine faults, at least 2f + 1 node-disjoint paths are needed between a source and destination node pair. However, often the faulty nodes\´ misbehavior manifests itself as a "disagreement" between information provided by the faulty node and its neighbors. This disagreement can be captured in the form of a conflict graph. Even though the conflict graph does not always allow us to identify faulty nodes precisely, we show that it can still be used to reduce the number of paths necessary for reliable communication (to smaller than 2f+1). We consider two strategies for using the node-disjoint paths for reliable delivery of messages: replication and coding across different paths. For each strategy, we propose iPath, a scheme to identify the optimal set of paths that needs to be used to achieve reliable communication for a given conflict graph.