2
Y. Amir, L. E. Moser, P. M. Melliar-Smith, D. A. Agarwal, P. Ciarfella
1. INTRODUCTION
Fault-tolerant distributed systems are b ecoming more imp ortant due to the increas-
ing demand for more reliable operation and improved p erformance. Maintaining
the consistency of replicated data and co ordinating the activities of coop erating
processors present substantial problems, which are made more dicult by concur-
rency, asynchrony, fault-tolerance, and real-time p erformance requirements. Exist-
ing fault-tolerant distributed systems that address these problems are dicult to
program, and exp ensive in the numb er of messages broadcast and/or computations
required. Recent protocols for fault-tolerant distributed systems [2; 5; 9; 12; 17]
employ the idea of placing a partial or total order on broadcast messages to simplify
the application programs and to reduce the communication and computation costs.
The Totem single-ring proto col supp orts high-performance fault-tolerant dis-
tributed systems that must continue to operate despite network partitioning and
remerging, and pro cessor failure and restart. Totem provides totally ordered mes-
sage delivery with low overhead, high throughput, and low latency using a logical
token-passing ring imp osed on a broadcast domain. The key to its high perfor-
mance is an eective ow control mechanism. Totem also provides rapid detection
of network partitioning and pro cessor failure together with reconguration and
membership services. Its novel mechanisms prevent delivery of messages in dier-
ent orders in dierent comp onents of a partitioned network, and provide accurate
information about which processors have delivered which messages. Earlier versions
of the Totem single-ring proto col are describ ed in [3; 11].
Programming the application is considerably simplied if messages are delivered
in total order rather than only in causal order, or if messages are delivered in causal
order rather than only in FIFO order. In prior systems, delivery of messages in
total order has b een more exp ensive than delivery of messages in causal order, and
delivery of messages in causal order has b een more expensive than FIFO delivery.
The Totem single-ring proto col can, however, deliver totally ordered messages with
high throughput at no greater cost than causally ordered messages or, indeed,
than reliable point-to-point FIFO messages. A total order on messages simplies
the application programming by reducing the risk of inconsistency when replicated
data are updated, and by resolving the contention for shared resources within the
system, such as the claiming of locks.
In Totem, messages are delivered in agreed order, which guarantees that pro ces-
sors deliver messages in a consistent total order and that, when a pro cessor delivers
a message, it has already delivered all prior messages originated within its current
conguration. Totem also provides delivery in safe order, which guarantees addi-
tionally that, when a processor delivers a message, it has determined that every
processor in the current conguration has received and will deliver the message un-
less that processor fails. Delivery of a message in agreed or safe order is requested
by the originator of the message.
Delivery in a consistent total order is not easy to achieve in distributed systems
that are sub ject to pro cessor failure and network partitioning. A failing pro cessor,
or a group of pro cessors that have become isolated, may deliver messages in an
order that is dierent from the order determined by other processors. As long as
those pro cessors remain failed or isolated, these inconsistencies are not apparent,
4星 · 超过85%的资源 需积分: 22 193 浏览量
2018-10-12
11:54:35
上传
评论
收藏 376KB PDF 举报 
do_er2019-10-09学习一下先
