A Cost-Benefit Approach to Fault Tolerant Communication and Information Access

About us
Technology Transfer
Secure Spread

Technical Report, July 2000


Our goal is to develop a Cost-Benefit framework for fault tolerant communication and information access that addresses extremely powerful adversaries that were never handled in the past. The project will develop the theory and algorithms required to overcome strong network attacks, while providing theoretically provable performance bounds. We will build a system that incorporates these algorithms, and that exhibits good performance in practice.


Our technical approach includes the following innovative topics:
  • Analysis of strong adversary models: In order to understand how robust our solutions must be, we need to first understand what is the model of possible attacks and errors. This project introduces a collection of adversary models. They range from a simple predictable slow adversary, to a somewhat limited "stable path" adversary (which allows communication over a path to be successfully completed), to a totally unpredictable adversary (which can selectively block traffic based on type, source, destination, etc.). Many of these models have not been considered in the literature so far.

  • New routing and dissemination protocols: We present a suite of novel routing protocols tailored to the above adversary models and prove that these protocols perform in a near-optimal manner. Specifically, we present novel solutions that, in case an operational path exists, will be able to select such a path with high probability and, in case such a path does not exist, will store and forward the packets. Our goal is to support the performance and correctness properties of these protocols by rigorous analysis. We aim our analysis not to assume anything about either the topology or the traffic patterns in the network, and not to assume a known correlation between past and future behavior of the adversary.

  • New replication protocol: When there is no theoretic possibility of communication, say in the case of a cut in the network, one can still continue the operation by making sure that the data is replicated in most areas, or at least in the areas where disconnection is likely. We will develop a suite of replication protocols that can handle a range of adversaries and can gracefully degrade performance and semantics as the network hostility increases.

  • A Cost-Benefit decision framework: This framework is used to select the most suitable protocol as network conditions change, both for network-level protocols such as routing and dissemination, and data-level protocols such as replication. The main idea is to consider the marginal benefit obtained by the application when consuming a given resource, versus the "opportunity cost" of using this resource. The latter is the benefit that may potentially be lost by other applications if this resource is committed. In the network level, the decision is based on application tolerance to delay, and the reliability of the network. In the data level, the decision is based on the cost of inaccessibility of data, the cost of updating replicas, and the synchronization cost of replication.

  • An overlay network architecture: We develop an overlay network architecture that will make these protocols practical since they are too complex to have any hope to be implemented in general Internet routers anytime soon.

Recent Accomplishments:

New Start

Current Plan:

Our plan for FY 2001 includes the following:
  • Network level resiliency: Algorithmic design and simulations - focusing on randomized path selection and gravitational flow.

  • Data level resiliency: Simulating different replication protocols with special focus on the active replication and the anti-entropy replication technique.

  • Cost benefit decision making: Algorithmic design - figuring out the specific interfaces and formulas for the network-level resiliency and the data-level resiliency domains.

  • Overlay network infrastructure: partial implementation of a core system providing the overlay network abstraction.

Technology Transfer:

New Start

Questions or comments to:
webmaster (at) dsn.jhu.edu
TEL: (410) 516-5562
FAX: (410) 516-6134
Distributed Systems and Networks Lab
Computer Science Department
Johns Hopkins University
3400 N. Charles Street Baltimore, MD 21218-2686