RELATED WORK

Active replication using reliable multicast is proposed in [14]. However, their approach is deadlock and livelock prone, since they do not use totally ordered multicast, that is, different clients can block a minority of the replicas and thus none of them can proceed. There is no scheduling policy, so whenever there is a conflict a transaction is aborted. Although the underlying protocols are more efficient, transaction abortions are more frequent. In [12] a different approach is presented to achieve active replication on a replicated database. The paper argues that total ordered multicast is expensive and they propose the use an optimistic total ordered multicast that it is less expensive. Optimistic multicast ordering consists in delivering the message when it is still unknown whether the total order is preserved. If later it is found out that a message was delivered in the wrong order and that this wrong ordering yielded a disordering of conflicting transactions, then the transaction executed in the wrong order is aborted. This approach provides a higher throughput but it has sometimes to redo transactions due to wrong ordering in the optimistic multicast. Our approach provides less throughput but it does not abort transactions resulting in a higher availability. They allow concurrency within the server by using predefined stored procedures where data accesses can be known in advance. This knowledge allows classifying transactions in conflict classes. Requests corresponding to different conflict classes can be run concurrently, due they will not conflict and the real interleaving among them is not important (in fact they will scheduled differently in each replica). However, classifying operations in conflict classes is not always possible what restricts the use of this approach. [20] also achieves concurrent replicas in a non-transactional setting based on a primary backup-approach. In this approach the primary receives the requests and processes them. The scheduler of the run-time system has been modified to annotate the non-deterministic scheduling decisions. Periodically, the primary checkpoints these decisions, as well as the requests it has processed. This approach, although it is more general, requires the modification of the underlying scheduler (in their proposal the run-time system of the gnat Ada 95 compiler) what most of the times will not be feasible. Even when this is possible, this is a very difficult and costly task. Another disadvantage of the approach is the need of checkpointing periodically that has a high cost. Finally, the possibility of losing processing in case of the primary failure decreases transaction availability.

Another approach in the borderline of active and passive replication is the one presented in [11]. In this work transactions are executed locally at one replica, and then the updates are totally ordered multicast to the other replicas. This total order is used as the serialization order. Due to the local execution of transactions violations of the serial order can happen thus it is necessary a certification phase. During this certification phase it can be found that conflicting transactions have violated the serial order (deduced from the total ordering). In this case transactions are aborted, otherwise they are committed by multicasting a commit message. The main advantage of this approach is that the work load is distributed among the replicas, as not all the replicas process all transactions. This approach is not abort free as transactions that violate the serialization order are aborted. From the availability point of view, this approach is less available than ours in that transactions can be aborted, and that a transaction that is being processed locally can be lost in the advent of a failure, as this transaction is only known locally. In our approach this cannot happen as all the replicas know all the transactions.




1999-11-17