Date Added: Apr 2013
The authors demonstrate the feasibility of end-to-end communication in highly unreliable networks. Modeling a network as a graph with vertices representing nodes and edges representing the links between them, they consider two forms of unreliability: unpredictable edge-failures and deliberate deviation from protocol specifications by corrupt nodes. they present a robust routing protocol for end-to-end communication that is simultaneously resilient to both forms of unreliability. In particular, they prove rigorously that their protocol is secure against the actions of the corrupt nodes, achieves correctness (Receiver gets all of the messages from Sender, in order and without modification), and enjoys provably optimal throughput performance, as measured using competitive analysis.