Optimistic total order in wide area networks

@inproceedings{citeulike:2270108, abstract = {Total order multicast greatly simplifies the implementation of fault-tolerant services using the replicated state machine approach. The additional latency of total ordering can be masked by taking advantage of spontaneous ordering observed in LANs: A tentative delivery allows the application to proceed in parallel with the ordering protocol. The effectiveness of the technique rests on the optimistic assumption that a large share of correctly ordered tentative deliveries offsets the cost of undoing the effect of mistakes. This paper proposes a simple technique which enables the usage of optimistic delivery also in WANs with much larger transmission delays where the optimistic assumption does not normally hold. Our proposal exploits local clocks and the stability of network delays to reduce the mistakes in the ordering of tentative deliveries. An experimental evaluation of a modified sequencer-based protocol is presented, illustrating the usefulness of the approach in fault-tolerant database management.}, author = {Sousa, A. and Pereira, J. and Moura, F. and Oliveira, R. }, booktitle = {Reliable Distributed Systems, 2002. Proceedings. 21st IEEE Symposium on}, citeulike-article-id = {2270108}, doi = {10.1109/RELDIS.2002.1180188}, journal = {Reliable Distributed Systems, 2002. Proceedings. 21st IEEE Symposium on}, keywords = {atomic-broadcast, concurrency-control, totally-ordered-multicast}, pages = {190--199}, posted-at = {2008-01-21 21:16:27}, priority = {0}, title = {Optimistic total order in wide area networks}, url = {http://dx.doi.org/10.1109/RELDIS.2002.1180188}, year = {2002} }

TY - CONF ID - citeulike:2270108 L3 - citeulike-article-id:2270108 TI - Optimistic total order in wide area networks T2 - Reliable Distributed Systems, 2002. Proceedings. 21st IEEE Symposium on JF - Reliable Distributed Systems, 2002. Proceedings. 21st IEEE Symposium on SP - 190 EP - 199 N2 - Total order multicast greatly simplifies the implementation of fault-tolerant services using the replicated state machine approach. The additional latency of total ordering can be masked by taking advantage of spontaneous ordering observed in LANs: A tentative delivery allows the application to proceed in parallel with the ordering protocol. The effectiveness of the technique rests on the optimistic assumption that a large share of correctly ordered tentative deliveries offsets the cost of undoing the effect of mistakes. This paper proposes a simple technique which enables the usage of optimistic delivery also in WANs with much larger transmission delays where the optimistic assumption does not normally hold. Our proposal exploits local clocks and the stability of network delays to reduce the mistakes in the ordering of tentative deliveries. An experimental evaluation of a modified sequencer-based protocol is presented, illustrating the usefulness of the approach in fault-tolerant database management. KW - atomic-broadcast KW - concurrency-control KW - totally-ordered-multicast AU - Sousa, A AU - Pereira, J AU - Moura, F AU - Oliveira, R PY - 2002/// UR - http://dx.doi.org/10.1109/RELDIS.2002.1180188 ER -