A Cost Benefit Approach to Fault Tolerant Communication and Information Access

Quarterly Technical Report, October 2000

Progress:

• Analysis of strong adversary models: We investigated an adversary that can fail and recover edges in an arbitrary manner, in contrast to traditional adversary models which leave the network stable for time long enough for the protocols to accomplish global communication.

• New routing and dissemination protocols: We devised initial routing protocols that accomplish the task of routing facing the above strong adversary model. Our protocols operate without using the concept of a global path, which is standard in the common "weak adversary" models. Moreover, the operation of these protocols is based solely on locally available knowledge, eliminating the need to build a global picture of the network state.

• New replication protocol: We have developed a general replication engine that allows consistent ordering of actions in a network that is prone to partitions and crashes. The main idea has several instances of the engine (several tens) strategically positioned in the network. The replicas maintain consistent state and recover from a wide range of possible faults. The engine software is now going through testing and evaluation.

  We have built some of the infrastructure that will allow us to test the replication engine, inducing faults into practical network settings. Currently, our tests are still configned to our lab.

• Overlay networks architecture: We started developing the basic building blocks for our overlay networks architecture. The first step was to develop Hop - a link level modified selective-repeat protocol that is TCP-fair, uses less CPU, and allows us full control over the forwarding of messages on the overlay network.

  We designed two alternative global flow control schemes. The first scheme is a cost benefit approach to buffer utilization in the overlay network routers. The second Scheme is a cost benefit approach to capacity utilization of the overlay links. We are still investigating the tradeoffs between these schemes.

Plans for Next Quarter:

• Network level resiliency: We plan to analyze specific techniques for single-source single-destination routing, and develop efficient routing methods for the weak adversary model. We expect that the final protocol will achieve performance comparable to algoritms that operate with global knowledge of current and future adversarial behavior.

• Data level resiliency: We plan to continue the validation of our general replication engine. We intend to use the CAIRN network to experiment with high latency wide area settings. Next, we plan to integrate the replication engine to an open source database, probably postgres or MySql.

  In addition, we plan to investigate building a global resilient file system as the first test case for data level resiliency. We will investigate building it on top of our replication engine to provide strict semantics for file access. This will go beyond the next quarter.

• Cost benefit decision making: We will continue developing the cost benefit framework to support global flow control on our overlay network architecture. We plan to investigate extending the cost benefit framework to support overlay network routing.

• Overlay network infrastructure: Our goal is to complete the global flow control mechanisms in our overlay network architecture. This will allow efficient dissemination of data that adapts to network conditions.