A Framework for Scalable Total Ordering Protocols
Original Publication Date: 2009-Dec-31
Included in the Prior Art Database: 2009-Dec-31
This document presents a new and innovative framework imposing a scalable way to exploits a tree-based topology in total ordering protocols. Scalability in this essence refers to the number of the “known processes” per node, regardles of the radical increase in the number of nodes. In addition, it also refers to the system resources and complexity that are required to maintain, modify or remove processes on the system due to reconfiguration.
Replication is a fundamental technology for providing fault tolerance and achieving high availability in information
systems. Total ordering messaging is a critical service to maintain consistency among all members in such
systems. Most total ordering protocols are designed for traditional distributed systems that contain a limited number
of processes. Nowadays,
we are facing a new era of emerging distributed systems
with a huge number of processes,
where the number of processes may be unknown a priori.
For example, the IBM
Blue Gene/L system includes ten of thousands of nodes.
THOR is based on a logical tree topology denoted VTR (
Virtual Tree of
where each node is a process that
can be executed on any number of the physical participating machines. The processes are classified into real and
virtual nodes. The real nodes are located at the leafs of the tree. They can send, receive and deliver data messages.
All the other nodes are considered
virtual nodes and are used mainly for routing purposes. The tree structure, along
with the two different processes types,
greatly enhance our framework's scalability
characteristics by allowing the leave/
join events to happen locally in sub-trees,
with no strict requirement for
reconfiguration of the entire tree.
we show later,
THOR can be implemented using any of the total order classes presented in . In order to easily
present our framework,
we chose here to focus our discussion on the fixed
sequester type of protocols.
Defago et al. classified the total ordering protocols into five classes: Fixed Sequencer, Moving Sequencer,
Privilege-Based, Communication History, and Destination Agreement.
Many protocols, such as the protocols in ] reside on a tree routing path (forest). Similarly to any protocol in
THOR, different nodes may have different roles. For instance, in each node on the path can potentially execute
actions similar to the multicasting (real) nodes in THOR. In contrary,
we chose to
differ the inner (virtual) nodes
from the multicasting nodes. Specifically,
we chose to place our real nodes at the
lowest level of the tree. The
reason is mainly due to the fact that this structure makes reconfiguration easier in
scenarios. By using the THOR framework,
occurs primarily at the deepest level of the sub-trees, affecting only the real nodes.
The existing of virtual nodes,
which support the routing and maintain the VTR's
structure, are hardly changed.
THOR sets the number of "known processes" to a fixed, bound number of processes per node,
while at the same time reduces the amount of time and system resources that are
required due to reconfiguration.
Limiting the number of "known processes" to a bound, preselected number yields the ability to anticipate the future
cost of the physical system resources. In addition, it also has the added value of obtaining simplicity at the