Distributed System Common Global Clock Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

In distributed system common global clock and shared memory does not exist, so knowledge is shared by passing messages between several sites. Reliable broadcast eventually delivers messages to all participating sites. Total order broadcast ensures that all messages must be delivered to all sites in same order and it is a stronger notion of reliable broadcast. Event-B is based on set theory and used event driven approach. For system-level analysis and modeling Event-B is a formal technique. In this technique system is gone through several stages for refinement. To specify total order broadcasting we introduce privilege based algorithm and refine it at the refinement level that only owner of the token can broadcast the messages in privilege based algorithm and detect failures like messages having same sequence number, token is not present for broadcasting a messages, higher sequence number message is is delivered before lower one.


Distributed system architecture consists of a collection of workstations and servers connected by a local area network and distribution middle ware. In other words heterogeneity of the network components that are separated and cooperate with each other for distributed computation. In distributed system common global clock and shared memory exist does not exist. Communication is done by passing messages between several sites where messages are delivered after arbitrary time delay. This problem can be dealt by relying on broadcast primitives that provide ordering guarantees on the delivery of messages. Total order broadcast ensures that all messages must be delivered to all sites in same order. It satisfies the total order requirements and essential for group communication services. We are using privileged based algorithm in which process can only send messages when they are allowed to do it. In system a special message or token is sent and only the owner of the token is allowed to send messages.

A total order broadcast is a reliable broadcast that delivers message in a same delivery order to all processes. In the step of refinement we are using acknowledgement of message to make sure that messages are not lost in between of the process and delivered successfully to its destination. We also identify that delivery order of message is not be same at all sites and higher sequence number messages is not delivered before lower sequence number messages.

Total Order Broadcast Service

Here we briefly discuss about total order broadcasting. We assume that there is a substrate layer providing basic broadcasting services.

I. Basic Broadcast Service:

In system any process is send its messages by using broadcast service. A broadcast message is received by all destined process at different time. Internally the causal delivery of messages is guaranteed by the broadcast service.

The basic broadcasting services receive the messages and keep causal order of messages and deliver them. In the system broadcasting service not guarantee the same delivery sequence of concurrent messages on all processes

II. Total Order Broadcast:

A Total order broadcast can be defined as a reliable broadcast that satisfies total order requirement. For concurrent messages causal order extends to total order.

Assume m1 and m2 are two total order broadcast messages-

If m1 causally precedes m2, then all machines deliver m1 before m2.

If machine p delivers m1 before m2 and m1 and m2 are concurrent messages, then machine q that belongs to the same partition with p delivers m1 before m2.

In other words if two processes p and q both deliver the messages m1 and m2then p delivers m1 before m2 if and only if q delivers m1 before m2.

Review of Total Order Protocols

In the absence of failures survey of total order broadcast algorithms is given. In algorithms there are three different roles those participating processes that are

Sender (from which a message originates)

Destination (to which a message is destined)

Sequencer (involved in ordering of messages)

According to these three different roles Total order protocols classifies in five different classes

Fixed sequencer

Moving sequencer

Privilege based

Communication history

Destination agreement

In Fixed Sequencer Algorithm single process is elected as a sequencer and responsible for ordering of messages on behalf of other processes in the system. Failure of this sequencer is not tolerated.

In Moving Sequencer Algorithm sequencer is not a fixed which means the role of sequencer is to be transferred between several processes for ordering of messages. It is a token based algorithm.

The idea behind privilege based algorithm is that the process can broadcast message only when they are granted to do it. At every moment if only one process is allowed to broadcast messages, then the total order can be easily set using a global sequence number. Generally privilege circulates among several processes in the form of token. Only owner of the token is allowed to broadcast messages. When a process wants to broadcast a message must wait until it receives the token messages. Then, it assigns a sequence number to each of its messages and sends them to all destinations. So sender updates the token and sends it to the next sender. Destination processes deliver messages in increasing sequence numbers.

In communication history algorithm, processes use historical information about message sending, reception and delivery to total order messages. The delivery order is determined by the senders. There are two variants that are Causal history and Deterministic merge.

In destination agreement algorithms, delivery order results from an agreement between destination processes. There are different variants of agreement:

Agreement on a message sequence number, Agreement on a message set, Agreement on the acceptance of a proposed message order.

Formal Method: Event-B

Event-B which is based on set theory. It used event driven approach. The event system is defined by its state and it contains a number of events. An event is consisting of three elements that are its name, guard and actions. For the occurrence of an event, guards are required. B uses abstract machine which encapsulate state and operations. Abstract machine consist set, constant and variable clauses. It also includes a design step called refinement step which is closer to an implementation. At each refinement state initialization event which has no guard helps to model the system such that new details are added.

Description of Model

For the reliable total ordering of messages fixed sequencer, moving sequencer, privilege based algorithm, communication history and destination agreement are used []. We consider privilege based algorithm which is also called token based algorithm because token is responsible for broadcasting of messages. In the abstract model we have used privilege based algorithm which allow to only one process to send messages at every moment so total order can easily be set using global sequence number and each site deliver the messages in total order. In the refinement model we introduce privilege based algorithm in which only owner of the token can broadcast its messages. When a process wants to broadcast a message must wait until it receives the token messages and destination processes deliver messages in increasing sequence numbers. In further refinement steps we detect failures like two different messages receive same sequence number and higher sequence number message delivered before the lower sequenced number messages and token is lost or not received by any process. We use following B notations:

B Symbols



Partial Function

Total Function

Element Of

For All

Natural Number

Domain Restriction

Power Set

There Exists

Abstract Model:

In the abstract model, we use privilege based algorithm to ensure total order delivery of messages. Here we have used privilege based algorithm which allow to only one process to send messages at every moment so total order can easily be set using global sequence number [ ].To define set of processes and messages in the system we use two sets PROCESS and MESSAGE. We use to declare some variables like sender, totalorder, tdeliver. Sender is defined as partial function from MESSAGE to PROCESS and mapping between them indicates that message m was sent by process p. The partial function ensures that message is associated with only one sender process. Invariant of sender is


The variable tdeliver is a relation between PROCESS and MESSAGE and indicates that a process p has delivered a message m in total order. Invariant of tdeliver is


The totalorder variable is a relation between MESSAGES and the mapping )indicate that message m1 is totally order before message m2. We use the invariant of totalorder is


In this machine a broadcast message is delivered to its sender as well as all other processes. It may be noticed that all delivered messages must be messages that have been sent. This is proof by following invariant


Initially all variables contain an empty set. Total ordering of message is define by

totalorder := totalorder(ran(tdeliver)*{mm})

For the total order delivery of message invariant is

Refinement Model: