InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

A Framework for Scalable Total Ordering Protocols

IP.com Disclosure Number: IPCOM000191360D
Original Publication Date: 2009-Dec-31
Included in the Prior Art Database: 2009-Dec-31
Document File: 6 page(s) / 62K

Publishing Venue



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.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 21% of the total text.

Page 1 of 6



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 [1]. 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.

Page 2 of 6

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
implementation phase.

System Mode...