Distributed and Parallel Computing

Q.1 } Explain Architectural styles of distributed System

            There area four different architectural styles, plus the hybrid architecture, when it comes to distributed systems. The basic idea is to organize logically different components, and distribute those computer over the various machine.

• Layered Architecture
• Object Based Architecture
• Data - centered Architecture
• Event Based Architecture
• Hybrid Architecture

1. Layered Architecture


            The layered architecture separates layers of components from each other, giving it a much more modular approach. A well known example for this is the OSI model that incorporates a layered architecture when interacting with each of the component . Each interaction is sequential where a layer will contact the adjacent layer and this process continues, until the request is been catered to. But in certain cases, the implementation can be made so that some layers will be skipped, which is called cross-layer coordination. Through cross-layer coordination , one can obtain better results due to performance increase.
                The layers on the bottom provide a service to the layers on the top. The request flows from top to bottom, whereas the response is sent from bottom to top. The advantage of using this approach is that, the calls always follow a predefined path, and that each layer can be easily replaced or modified without affecting the entire architecture. The following image is the basic idea of a layered architecture style.

2.Object Based Architecture

            This architecture style is based on loosely coupled arrangement of objects. This has no specific architecture like layers. Like in layers, this does not have a sequential set of steps that needs to as objects, where each object can interact with other objects through a given connector or interface. These area much more direct where all the different components can interact directly with other components through a direct method call.

                As shown in the above image, communication between object happen as method invocation. These are generally called Remote Procedure Calls (RPC). Some popular examples are java RMI , Web Services and REST API Calls. This is following properties:-
This architecture style is less structured.
Component = object
connector = RPC or RMI
                When decoupling these processes in space, people wanted the components to be anonymous and replaceable. And the synchronization process needed to be asynchronous, which has led to Data Centered Architecture and Event Based Architectures.


3.Data Centered Architecture

                This architecture is based on a data center, where the primary communication happens via a central data repository. This common repository can be either active or passive. This is more like a producer consumer problem. The producers produce items to a common data store and the consumers can request data from it. This common repository, could even be a simple database. But the idea is that, the communication between objects happening through this shared common storage. This supports different components by providing a persistent storage space for those component. All the information related to the nodes in the system are stored in this persistent storage. In event-based architectures, data is only sent and received by those components who have already subscribed.
Some popular examples are distributed file systems, producer consumer, and web based data services.

4.Event Based Architecture

              The entire communication in this kind of a system happens through events. When an event is generated, it will be sent to the bus system. With this, everyone else will be notified telling that such an event has occurred. So, if anyone is interested, that node can pull the event from the bus and use it. Sometimes these events could be data, or even URLs to resources. So the receiver can access whatever the information is given in the event and process accordingly. processes communicate through the propagation of events.
                These events occasionally carry data. An advantage in this architectural style is that, components are loosely coupled. So it is easy to add, remove and modify components in the system. Some examples are, publisher - subscriber system, Enterprise Services Bus (ESB) and akka.io.
One major advantage is that, these heterogeneous components can contact the bus, through any communication protocol. But an ESB or a specific bus, has the capability to handle any type of incoming request and process accordingly

This architectural style is based on the publisher-subscriber architecture. Between each node there is no direct communication or coordination. Instead, objects which are subscribed to the service communicate through the event bus.


The event based architecture supports, several communication styles.

• Publisher-subscriber
• Broadcast
• Point-to-Point

The major advantages of this architecture is that the Components are decoupled in space - loosely coupled.



Q.2 } Explain Cluster Computing

            Cluster computing refers that many of the computers connected on a network and they perform like a single entity. Each computer that is connected to the network is called a node. Cluster computing offers solutions to solve complicated problems by providing faster computational speed, and enhanced data integrity. The connected computers execute operations all together thus creating the impression like a single system (virtual machine). This process is termed as transparency of the system. Based on the principle of distributed systems, this networking technology performs its operations. And here, LAN is the connection unit. This process is defined as the transparency of the system. Cluster computing goes with the features of:

• All the connected computers are the same kind of machines
• They are tightly connected through dedicated network connections
• All the computers share a common home directory.

Types of Cluster Computing

• Cluster load balancing
• High–Availability clusters
• High-performance clusters

1. Cluster Load Balancing

            Load balancing clusters are employed in the situations of augmented network and internet utilization and these clusters perform as the fundamental factor. This type of clustering technique offers the benefits of increased network capacity and enhanced performance. Here the entire nodes stay as cohesive with all the instance where the entire node objects are completely attentive of the requests those are present in the network. All the nodes will not operate in a single process whereas they readdress the requests individually as they arrive depending on the scheduler algorithm.

2. High-availability clusters
          

            These are also termed as failover clusters. Computers so often faces failure issues. So, High Availability comes in line with the augmenting dependency of computers as computers hold crucial responsibility in many of the organizations and applications. In this approach, redundant computer systems are utilized in the situation of any component malfunction. So, when there is a single point malfunction, the system seems to be completely reliable as the network has redundant cluster elements.

3. High-performance cluster

            This networking approach utilizes supercomputers to resolve complex computational problems. Along with the management of IO-dependent applications like web services, high-performance clusters are employed in computational models of climate and in-vehicle breakdowns. More tightly connected computer clusters are developed for work that might consider “supercomputing”.

Advantages of Cluster

• Cost efficacy – Even mainframe computers seems to be extremely stable, cluster computing is more in implementation because of their cost-effectiveness and economical. Also, these systems provide enhanced performance than that of mainframe computer networks.
• Expandability – The next crucial advantage of this cluster computing is its enhanced scalability and expandability. As they instantiate the prospect to combine multiple additional resources or the networks to the prevailing computer system.
• Flexibility – Cluster computing can be upgraded to the superior specification or extended through the addition of additional nodes (computer systems).

Applications

• Cluster computing can be implemented in weather modeling
• Stands as support in-vehicle breakdown and nuclear simulations
• Used in image processing and in electromagnetics too
• Perfect to be used in the applications of astrophysics, aerodynamics and in data mining
• Assist to solve complex computational problems
• Holds the flexibility to allocate workload as small data portions and which is called grid computing.

Q.3 } Explain Grid Computing.

            

Grid Computing can be defined as a network of computers working together to perform a task that would rather ne difficult for a single machine. All machine on that network work under the same protocol to act like a virtual supercomputer. Th task that they work on may include analysing huge datasets or simulating situation which require high computing power. Computer on the network contribute resources like processing power and storage capacity to the network. Grid Computing is a subset of distributed computing, where a virtual super computer comprises of machines on a network connected by some bus, mostly Ethernet or sometimes the internet. It can also be seen as a form of Parallel Computing where instead of many CPU cores on a single machine, it contains multiple cores spread across various locations. The concept of grid computing isn't new, but it is not yet perfected as there are no standard rules and protocols established and accepted by people.



Working:

A Grid computing network mainly consists of these three types of machines

1.Control Node:-
A computer usually a server or a group of servers which administrates the whole network and keeps the accounts of the resources in the network pool.


2. Provider:
The computer which contributes it's resources in the network resource pool.

3.User:
The computer that uses the resources on the network.

            When a computer makes a request for resources to the control node, control node gives the user access to the resources available on the network. When it is not in use it should ideally contribute it’s resources to the network. Hence a normal computer on the node can swing in between being a user or a provider based on it’s needs. The nodes may consist of machines with similar platforms using same OS called homogenous networks, else machines with different platforms running on various different OS called heterogenous networks. This is the distinguishing part of grid computing from other distributed computing architectures.

            For controlling the network and it’s resources a software/networking protocol is used generaly known as Middleware. This is responsible for administrating the network and the control nodes are merely it’s executors. As a grid computing system should use only unused resources of a computer, it is the job of the control node that any provider is not overloaded with tasks.

Advantages of Grid Computing:

1. It is not centralized, as there are no servers required, except the control node which is just used for controlling and not for processing.

2. Multiple heterogenous machines i.e. machines with different Operating Systems can use a single grid computing network.

3. Tasks can be performed parallely accross various physical locations and the users don’t have to pay for it(with money).

Q.4 } Advantages of threads for distributed system

            The program is divided into different tasks using threads. These tasks give the illusion of running parallel but are carried out one after the other. Thread has a program counter, registers, and stack. The program counter has the information of all the tasks and the timing, registers save the current working variables and stack stores the history of execution.

            Information such as code and data related and the open files are shared between threads. When changes are made in one thread, the alterations are seen by other threads as well. Threads in the same process share the memory space and address space.

Advantages of threads:

• Reduce context switching.
• Increase processing speed.
• Don’t need for inter-process communication.
• Threads minimize the context switching time.
• Use of threads provides concurrency within a process.
• Efficient communication.
• It is more economical to create and context switch threads.
• Threads allow utilization of multiprocessor architectures to a greater scale and efficiency.

Q.5} Virtualization in distributed systems

            Threads and processes can be seen as a way to do more things at the same time. In effect,
they allow us build (pieces of) programs that appear to be executed simultaneously. On a
single-processor computer, this simultaneous execution is, of course, an illusion. As there is
only a single CPU, only an instruction from a single thread or process will be executed at a
time. By rapidly switching between threads and processes, the illusion of parallelism is created.
This separation between having a single CPU and being able to pretend there are more can be
extended to other resources as well, leading to what is known as resource virtualization. This
virtualization has been applied for many decades, but has received renewed interest as
(distributed) computer systems have become more commonplace and complex, leading to the
situation that application software is mostly always outliving its underlying systems software
and hardware.
            Virtualization can take place in two different ways. First, we can build a runtime system that
essentially provides an abstract instruction set that is to be used for executing applications.
Instructions can be interpreted (as is the case for the Java runtime environment), but could also
be emulated as is done for running Windows applications on UNIX platforms. Note that in the
latter case, the emulator will also have to mimic the behavior of system calls, which has proven
to be generally far from trivial. This type of virtualization leads to what Smith and Nair (2005)
call a process virtual machine, stressing that virtualization is done essentially only for a single
process.
            An alternative approach toward virtualization is to provide a system that is essentially
implemented as a layer completely shielding the original hardware, but offering the complete
instruction set of that same (or other hardware) as an interface. Crucial is the fact that this
interface can be offered simultaneously to different programs. As a result, it is now possible to
have multiple, and different operating systems run independently and concurrently on the same
platform.

Q.6} Code migration

            There are situations in which passing programs, sometimes even while they are being executed, simplifies the design of a distributed system.To start with by considering different approaches to code migration, followed by a discussion on how to deal with the local resources that a migrating program uses.Traditionally, code migration in distributed systems took place in the form of process migration in which an entire process was moved from one machine to another.Moving a running process to a different machine is a costly and intricate task, and there had better be a good reason for doing so.
That reason has always been performance.The basic idea is that overall system performance can be improved if processes are moved from heavily-loaded to lightly-loaded machines.Load is often expressed in terms of the CPU queue length or CPU utilization, but other performance indicators are used as well.Support for code migration can also help improve performance by exploiting parallelism, but without the usual intricacies related to parallel programming.A typical example is searching for information in the Web.It is relatively simple to implement a search query in the form of a small mobile program, called a mobile agent that moves from site to site.By making several copies of such a program, and sending each off to different sites, we may be able to achieve a linear speedup compared to using just a single program instance.

Q.7} RPC

            A remote procedure call is an interprocess communication technique that is used for client-server based applications. It is also known as a subroutine call or a function call.
            A client has a request message that the RPC translates and sends to the server. This request may be a procedure or a function call to a remote server. When the server receives the request, it sends the required response back to the client. The client is blocked while the server is processing the call and only resumed execution after the server is finished.

The sequence of events in a remote procedure call are given as follows −

• The client stub is called by the client.
• The client stub makes a system call to send the message to the server and puts the parameters in the message.
• The message is sent from the client to the server by the client’s operating system.
• The message is passed to the server stub by the server operating system.
• The parameters are removed from the message by the server stub.
• Then, the server procedure is called by the server stub.

A diagram that demonstrates this is as follows −

Advantages of Remote Procedure Call

• Some of the advantages of RPC are as follows −
• Remote procedure calls support process oriented and thread oriented models.
• The internal message passing mechanism of RPC is hidden from the user.
• The effort to re-write and re-develop the code is minimum in remote procedure calls.
• Remote procedure calls can be used in distributed environment as well as the local environment.
• Many of the protocol layers are omitted by RPC to improve performance. 

Disadvantages of Remote Procedure Call

• Some of the disadvantages of RPC are as follows −
• The remote procedure call is a concept that can be implemented in different ways. It is not a standard.
• There is no flexibility in RPC for hardware architecture. It is only interaction based.
• There is an increase in costs because of remote procedure call.

Q.8} Message-Oriented Transient Communication

            Many distributed systems and applications are built directly on top of the simple message-
oriented model offered by the transport layer. To better understand and appreciate the
message-oriented systems as part of middleware solutions, we first discuss messaging through
transport-level sockets.


Berkeley Sockets
            Special attention has been paid to standardizing the interface of the transport layer to allow
programmers to make use of its entire suite of (messaging) protocols through a simple set of
primitives. Also, standard interfaces make it easier to port an application to a different machine.
As an example, we briefly discuss the sockets interface as introduced in the 1970s in Berkeley
UNIX. Another important interface is XTI, which stands for the X/Open Transport Interface,
formerly called the Transport Layer Interface (TLI), and developed by AT&T. Sockets and XTI
are very similar in their model of network programming, but differ in their set of primitives.
Conceptually, a socket is a communication end point to which an application can write data that
are to be sent out over the underlying network, and from which incoming data can be read. A
socket forms an abstraction over the actual communication end point that is used by the local
operating system for a specific transport protocol. In the following text, we concentrate on the
socket primitives for TCP,

Primitive	Meaning
Socket	Create a new communication end point
Bind	Attach a local address to a socket
Listen	willingness to accept connections
Accept	Block caller until a connection request arrives
Connect	Actively attempt to establish a connection
Send	Send some data over the connection
Receive	Receive some data over the connection
Close	Release the connection

Q.9} Message-Oriented Persistent Communication

            We now come to an important class of message-oriented middleware services, generally
known as message-queuing systems, or just Message-Oriented Middleware (MOM). Message-
queuing systems provide extensive support for persistent asynchronous communication. The
essence of these systems is that they offer intermediate-term storage capacity for messages,
without requiring either the sender or receiver to be active during message transmission. An
important difference with Berkeley sockets and MPI is that message-queuing systems are
typically targeted to support message transfers that are allowed to take minutes instead of
seconds or milliseconds. We first explain a general approach to message-queuing systems,
and conclude this section by comparing them to more traditional systems, notably the Internet
e-mail systems.

Message-Queuing Model
            The basic idea behind a message-queuing system is that applications communicate by
inserting messages in specific queues. These messages are forwarded over a series of
communication servers and are eventually delivered to the destination, even if it was down
when the message was sent. In practice, most communication servers are directly connected to
each other. In other words, a message is generally transferred directly to a destination server.
In principle, each application has its own private queue to which other applications can send
messages. A queue can be read only by its associated application, but it is also possible for
multiple applications to share a single queue.

             An important aspect of message-queuing systems is that a sender is generally given only the
guarantees that its message will eventually be inserted in the recipient's queue. No guarantees
are given about when, or even if the message will actually be read, which is completely
determined by the behavior of the recipient.

Primitive	Meaning
Put	Append a message to a specified queue
Get	Block until the specified queue is nonempty and remove the first message
Poll	Check a specified queue for message and remove the first Never block
Notify	Install a handler to be called when a message is put into the specified queue

            The put primitive is called by a sender to pass a message to the underlying system that is to be
appended to the specified queue. As we explained, this is a nonblocking call. The get primitive
is a blocking call by which an authorized process can remove the longest pending message in
the specified queue. The process is blocked only if the queue is empty. Variations on this call
allow searching for a specific message in the queue, for example, using a priority, or a
matching pattern. The nonblocking variant is given by the poll primitive. If the queue is empty,
or if a specific message could not be found, the calling process simply continues.

Q.10} Lamport’s Election algorithm

This algorithm applies to system where every process can send a message to every other process in the system.

Algorithm 

– Suppose process P sends a message to the coordinator.

1. If coordinator does not respond to it within a time interval T, then it is assumed that coordinator has failed.

2. Now process P sends election message to every process with high priority number.

3. It waits for responses, if no one responds for time interval T then process P elects itself as a coordinator.

4. Then it sends a message to all lower priority number processes that it is elected as their new coordinator.

5. However, if an answer is received within time T from any other process Q,

            (I) Process P again waits for time interval T’ to receive another message from Q that it has been             elected as coordinator.

            (II) If Q doesn’t responds within time interval T’ then it is assumed to have failed and algorithm             is restarted.

Q.11} Ways to handle Mutual exclusion in distributed system

            Mutual exclusion is a concurrency control property which is introduced to prevent race conditions. It is the requirement that a process can not enter its critical section while another concurrent process is currently present or executing in its critical section i.e only one process is allowed to execute the critical section at any given instance of time.

Requirements of Mutual exclusion Algorithm:

• No Deadlock:-Two or more site should not endlessly wait for any message that will never arrive. 
• No Starvation:-Every site who wants to execute critical section should get an opportunity to execute it in finite time. Any site should not wait indefinitely to execute critical section while other site are repeatedly executing critical section
• Fairness:-Each site should get a fair chance to execute critical section. Any request to execute critical section must be executed in the order they are made i.e Critical section execution requests should be executed in the order of their arrival in the system.
• Fault Tolerance:-In case of failure, it should be able to recognize it by itself in order to continue functioning without any disruption.

Solution to distributed mutual exclusion:
            As we know shared variables or a local kernel can not be used to implement mutual exclusion in distributed systems. Message passing is a way to implement mutual exclusion. Below are the three approaches based on message passing to implement mutual exclusion in distributed systems:

Token Based Algorithm:

• A unique token is shared among all the sites.
• If a site possesses the unique token, it is allowed to enter its critical section
• This approach uses sequence number to order requests for the critical section.
• Each requests for critical section contains a sequence number. This sequence number is used to distinguish old and current requests.

Non-token based approach:

•  A site communicates with other sites in order to determine which sites should execute critical section next. This requires exchange of two or more successive round of messages among sites.
• This approach use timestamps instead of sequence number to order requests for the critical section.
• When ever a site make request for critical section, it gets a timestamp. Timestamp is also used to resolve any conflict between critical section requests.

Quorum based approach:

• Instead of requesting permission to execute the critical section from all other sites, Each site requests only a subset of sites which is called a quorum.
• Any two subsets of sites or Quorum contains a common site.
• This common site is responsible to ensure mutual exclusion

Q.12} Issues to be addressed in designing a server

The distributed information system is defined as “a number of interdependent computers linked by a network for sharing information among them”. A distributed information system consists of multiple autonomous computers that communicate or exchange information through a computer network.

Design issues of distributed system –

• Heterogeneity : Heterogeneity is applied to the network, computer hardware, operating system and implementation of different developers. A key component of the heterogeneous distributed system client-server environment is middleware. Middleware is a set of service that enables application and end-user to interacts with each other across a heterogeneous distributed system.
• Openness: The openness of the distributed system is determined primarily by the degree to which new resource sharing services can be made available to the users. Open systems are characterized by the fact that their key interfaces are published. It is based on a uniform communication mechanism and published interface for access to shared resources. It can be constructed from heterogeneous hardware and software.
• Scalability: Scalability of the system should remain efficient even with a significant increase in the number of users and resources connected.
• Security : Security of information system has three components Confidentially, integrity and availability. Encryption protects shared resources, keeps sensitive information secrets when transmitted.
• Failure Handling : When some faults occur in hardware and the software program, it may produce incorrect results or they may stop before they have completed the intended computation so corrective measures should to implemented to handle this case.
• Failure handling is difficult in distributed systems because the failure is partial i, e, some components fail while others continue to function.
• Concurrency: There is a possibility that several clients will attempt to access a shared resource at the same time. Multiple users make requests on the same resources, i.e read, write, and update. Each resource must be safe in a concurrent environment. Any object that represents a shared resource a distributed system must ensure that it operates correctly in a concurrent environment.
• Transparency : Transparency ensures that the distributes system should be perceived as the single entity by the users or the application programmers rather than the collection of autonomous systems, which is cooperating. The user should be unaware of where the services are located and the transferring from a local machine to a remote one should be transparent.

Q.13} Stored multimedia data from server to client

            Multimedia storage servers provide access to multimedia objects including text, images, audio, and video. The design of such servers fundamentally differs from conventional servers due to:

(1) the real-time storage and retrieval requirements, as well as

(2) the large storage space and data transfer rate requirements of digital multimedia. In this paper, we present an overview of the architectures and algorithms required for designing digital multimedia storage servers.
    
            Multimedia distribution products allow you to send Video, Audio and sometimes serial data (RS-232 or USB) over distances of hundreds of meters to one or more locations. They generally utilise standard CatX infrastructure cable and can offer extensions to distances of up to 300m.

            VGA based Multimedia distribution products are similar in many ways to KVM extenders. They extend the output from a computer to a VGA monitor or projector located at a distance. The main differences are that they do not transmit keyboard and mouse data and that they often split the video and audio feeds for point to multi-point distribution applications while KVM extenders are generally point to point products.

• VGA based Multimedia extension:-Because VGA based Multimedia extension products use very similar video extension technology to CatX KVM extenders, many of the same technical recommendations apply. For example, when using Cat5e or Cat6 cable you may need a product that compensates for skew/colour drift, and you should always use solid core cable, and shielded cable if recommended in the product specifications. You can find more information about these recommendations in our Black Box Explains Video over Cat5 Cable. 

• Ideal for use:-These products are ideal for use in many digital signage applications and for interactive displays such as information counters and booths. The serial data component can be used to provide touch screen support and the high quality graphics and audio are perfect for the delivery of clear, high impact information and advertising. 

            Video based Multimedia distribution products send Video and Audio to TV type displays rather than computer monitors. The simplest distribution products of this type use video and audio baluns and hubs. These convert composite video, CCTV or component video from devices like VCRs, CCTV cameras and satellite receivers to Cat5 for transmission over long distances (more than 700 meters in some cases). There are even baluns available that will send Video, Audio and IR remote control data and these are ideal for small office or home cinema solutions.

            Distribution amplifiers and video switches are available for larger installations. Using these products it is possible build video networks with very large numbers of displays.



Popular applications:

• Schools: These products have many applications in schools for the delivery of time table information, educational content and even video and music at break times.
• Retail: There is huge potential for the use of digital signage as a means of delivering high impact advertising to customers in the store. Multimedia extenders are a low cost, plug and play solution for small to medium sized applications. They are also ideal for providing the last hop connectivity between play out equipment and displays in larger IP based solutions.
• Interactive displays: Often the computers driving the interactive displays (e.g. touch screens) found in some waiting rooms, reception areas, town halls and shopping centres can not be placed near to the display for security and maintenance reasons. A Multimedia extender allows the computer to be placed in secure location at a convenient distance from the display.
• Industrial Monitoring: A computer collecting industrial data or monitoring industrial processes may be located in an area uncomfortable or hazardous to people. Multimedia extenders can be used to view these devices from a safe and comfortable distance.
• Corporate: The live broadcast of news and events in reception areas, canteens and lobbies in corporate buildings is becoming increasingly popular.
• Whatever your application our engineers will be able to advise you on the best solution to fit your requirements.

Q.14}Centralized synchronization mechanisms

            The most straightforward way to achieve mutual exclusion in a distributed system is to simulate
how it is done in a one-processor system. One process is elected as the coordinator. Whenever
a process wants to access a shared resource, it sends a request message to the coordinator
stating which resource it wants to access and asking for permission. If no other process is
currently accessing that resource, the coordinator sends back a reply granting permission

Process 1 asks the coordinator for permission to access a shared resource. Permission is granted. (b) Process 2 then asks permission to access the same resource. The coordinator does not reply. (c) When process 1 releases the resource, it tells the coordinator, which then replies to 2. Now suppose that another process, 2 asks for permission to access the resource. The coordinator knows that a different process is already at the resource, so it cannot grant permission. The exact method used to deny permission is system dependent. In Fig. 6- 14(b), the coordinator just refrains from replying, thus blocking process 2, which is waiting for a reply. Alternatively, it could send a reply saying "permission denied." Either way, it queues the request from 2 for the time being and waits for more messages. When process 1 is finished with the resource, it sends a message to the coordinator releasing its exclusive access The coordinator takes the first item off the queue of deferred requests and sends that process a grant message. If the process was still blocked (i.e., this is the first message to it), it unblocks and accesses the resource. If an explicit message has already been sent denying permission, the process will have to poll for incoming traffic or block later. Either way, when it sees the grant, it can go ahead as well. The centralized approach also has shortcomings. The coordinator is a single point of failure, so if it crashes, the entire system may go down. If processes normally block after making a request, they cannot distinguish a dead coordinator from "permission denied" since in both cases no message comes back.


Q.15} Decentralized synchronization algorithm

            single coordinator is often a poor approach. Let us take a look at fully decentralized
solution. Lin et al. (2004) propose to use a voting algorithm that can be executed using a DHT-
based system. In essence, their solution extends the central coordinator in the following way.
Each resource is assumed to be replicated n times. Every replica has its own coordinator for
controlling the access by concurrent processes.
whenever a process wants to access the resource, it will simply need to get a
majority vote from m > n/2 coordinators. Unlike in the centralized scheme discussed before, we
assume that when a coordinator does not give permission to access a resource (which it will do
when it had granted permission to another process), it will tell the requester.
This scheme essentially makes the original centralized solution less vulnerable to failures of a
single coordinator. The assumption is that when a coordinator crashes, it recovers quickly but will have forgotten any vote it gave before it crashed.
            Another way of viewing this is that a coordinator resets itself at arbitrary moments. The risk that we are taking is that a reset will make the coordinator forget that it had previously granted permission to some process to access the resource. As a consequence, it may incorrectly grant this permission again to another process after its recovery.


Lets P is probability
Reset during time interval Δt.
The probability P [k ] that k out of m coordinators reset during the same interval is then

Given that at least 2m - n coordinators need to reset in order to violate the correctness of the
voting mechanism, the probability that such a violation occurs is then .


Q.16} Distributed algorithm

            The Distributed algorithm having a probabilistically correct algorithm is just not good enough. So researchers have looked for deterministic distributed mutual exclusion algorithms. Lamport's 1978 paper on clock synchronization presented the first one. Ricart and Agrawala (1981) made it more efficient. In this section we will describe their method. Ricart and Agrawala's algorithm requires that there be a total ordering of all events in the system. That is, for any pair of events, such as messages, it must be unambiguous which one actually happened first. Lamport's algorithm presented in Sec. 6.2.1 is one way to achieve this ordering and can be used to provide timestamps for distributed mutual exclusion. The algorithm works as follows. When a process wants to access a shared resource, it builds a message containing the name of the resource, its process number, and the current (logical) time. It then sends the message to all other processes, conceptually including itself. The sending of messages is assumed to be reliable; that is, no message is lost. When a process receives a request message from another process, the action it takes depends on its own state with respect to the resource named in the message. Three different cases have to be clearly distinguished:

1. If the receiver is not accessing the resource and does not want to access it, it sends back an
OK message to the sender.
2. If the receiver already has access to the resource, it simply does not reply. Instead, it queues
the request.
3. If the receiver wants to access the resource as well but has not yet done so, it compares the
timestamp of the incoming message with the one contained in the message that it has sent
everyone. The lowest one wins. If the incoming message has a lower timestamp, the receiver
sends back an OK message. If its own message has a lower timestamp, the receiver queues
the incoming request and sends nothing.

Q.17} Token ring algorithm 

            In this algorithm it is assumed that all the processes in the system are organized in a logical ring. The figure blow describes the structure.

• The ring positions may be allocated in numerical order of network addresses and is unidirectional in the sense that all messages are passed only in clockwise or anti-clockwise direction.
• When a process sends a request message to current coordinator and does not receive a reply within a fixed timeout, it assumes the coordinator has crashed. It then initializes the ring and process Pi is given a token.
• The token circulates around the ring. It is passed from process k to k+1 in point to point messages. When a process acquires the token from its neighbor it checks to see if it is attempting to enter a critical region. If so the process enters the region does all the execution and leaves the region. After it has exited it passes the token along the ring. It is not permitted to enter a second critical region using the same token.
• If a process is handed the token by its neighbor and is not interested in entering a critical region it just passes along. When no processes want to enter any critical regions the token just circulates at high speed around the ring.
• Only one process has the token at any instant so only one process can actually be in a critical region. Since the token circulates among the process in a well-defined order, starvation cannot occur.
• Once a process decides it wants to enter a critical region, at worst it will have to wait for every other process to enter and leave one critical region.
• The disadvantage is that if the token is lost it must be regenerated. But the detection of lost token is difficult. If the token is not received for a long time it might not be lost but is in use.

Q.19} Parallel Computer Memory Architectures, advantages and disadvantages of each

            Parallel processing has been developed as an effective technology in modern computers to meet the demand for higher performance, lower cost and accurate results in real-life applications. Concurrent events are common in today’s computers due to the practice of multiprogramming, multiprocessing, or multicomputing

• Computer Development Milestones − There is two major stages of development of computer - mechanical or electromechanical parts. Modern computers evolved after the introduction of electronic components. High mobility electrons in electronic computers replaced the operational parts in mechanical computers. For information transmission, electric signal which travels almost at the speed of a light replaced mechanical gears or levers.
• Elements of Modern computers − A modern computer system consists of computer hardware, instruction sets, application programs, system software and user interface.
• Evolution of Computer Architecture − In last four decades, computer architecture has gone through revolutionary changes. We started with Von Neumann architecture and now we have multicomputers and multiprocessors.
• Performance of a computer system − Performance of a computer system depends both on machine capability and program behavior. Machine capability can be improved with better hardware technology, advanced architectural features and efficient resource management. Program behavior is unpredictable as it is dependent on application and run-time conditions

two types of parallel computers

1. Multiprocessors
2. Multicomputers

1.Shared Memory Multicomputer 

• Uniform Memory Access (UMA) :- In this model, all the processors share the physical memory uniformly. All the processors have equal access time to all the memory words. Each processor may have a private cache memory. Same rule is followed for peripheral devices. 
  
  When all the processors have equal access to all the peripheral devices, the system is called a symmetric multiprocessor. When only one or a few processors can access the peripheral devices, the system is called an asymmetric multiprocessor. 
• Non-uniform Memory Access (NUMA) :- In NUMA multiprocessor model, the access time varies with the location of the memory word. Here, the shared memory is physically distributed among all the processors, called local memories. The collection of all local memories forms a global address space which can be accessed by all the processors. 
• Cache Only Memory Architecture (COMA) :- The COMA model is a special case of the NUMA model. Here, all the distributed main memories are converted to cache memories 

2. Distributed - Memory Multicomputers − A distributed memory multicomputer system consists of multiple computers, known as nodes, inter-connected by message passing network. Each node acts as an autonomous computer having a processor, a local memory and sometimes I/O devices. In this case, all local memories are private and are accessible only to the local processors. This is why, the traditional machines are called no-remote-memory-access (NORMA) machines.

Advantages

• Parallel computing saves time, allowing the execution of applications in a shorter wall-clock time.
• Solve Larger Problems in a short point of time.
• Compared to serial computing, parallel computing is much better suited for modeling, simulating and understanding complex, real-world phenomena.
• Throwing more resources at a task will shorten its time to completion, with potential cost savings. Parallel computers can be built from cheap, commodity components.

Disadvantages 

• Various code tweaking has to be performed for different target architectures for improved performance.
• Better cooling technologies are required in case of clusters.
• Power consumption is huge by the multi-core architectures.
• Programming to target Parallel architecture is a bit difficult but with proper understanding and practice, you are good to go.

Q.20} Distributed mutual exclusion algorithm suggested by Ricart and Agrawala

            Ricart–Agrawala algorithm is an algorithm to for mutual exclusion in a distributed system proposed by Glenn Ricart and Ashok Agrawala. This algorithm is an extension and optimization of Lamport’s Distributed Mutual Exclusion Algorithm. Like Lamport’s Algorithm, it also follows permission based approach to ensure mutual exclusion.

In this algorithm:

• Two type of messages ( REQUEST and REPLY) are used and communication channels are assumed to follow FIFO order.
• A site send a REQUEST message to all other site to get their permission to enter critical section.
• A site send a REPLY message to other site to give its permission to enter the critical section.
• A timestamp is given to each critical section request using Lamport’s logical clock.
• Timestamp is used to determine priority of critical section requests. Smaller timestamp gets high priority over larger timestamp. The execution of critical section request is always in the order of their timestamp.

Algorithm:

• To enter Critical section:
• When a site Si wants to enter the critical section, it send a timestamped REQUEST message to all other sites.
• When a site Sj receives a REQUEST message from site Si, It sends a REPLY message to site Si if and only if
• Site Sj is neither requesting nor currently executing the critical section.
• In case Site Sj is requesting, the timestamp of Site Si‘s request is smaller than its own request.Otherwise the request is deferred by site Sj.
• To execute the critical section:
• Site Si enters the critical section if it has received the REPLY message from all other sites.
• To release the critical section:
• Upon exiting site Si sends REPLY message to all the deferred requests.

Message Complexity:
            Ricart–Agrawala algorithm requires invocation of 2(N – 1) messages per critical section execution. These 2(N – 1) messages involves

1. (N – 1) request messages
2. (N – 1) reply messages

Drawbacks of Ricart–Agrawala algorithm:

• Unreliable approach: failure of any one of node in the system can halt the progress of the system. In this situation, the process will starve forever.The problem of failure of node can be solved by detecting failure after some timeout. 

Performance:

• Synchronization delay is equal to maximum message transmission time
• It requires 2(N – 1) messages per Critical section execution

Q.21} Message passing interface, important message-passing primitives of MPI

            The message passing interface (MPI) is a standardized means of exchanging messages between multiple computers running a parallel program across distributed memory.
            In parallel computing, multiple computers -- or even multiple processor cores within the same computer -- are called nodes. Each node in the parallel arrangement typically works on a portion of the overall computing problem. The challenge then is to synchronize the actions of each parallel node, exchange data between nodes and provide command and control over the entire parallel cluster. The message passing interface defines a standard suite of functions for these tasks.
            MPI is not endorsed as an official standard by any standards organization such as IEEE or ISO, but it is generally considered to be the industry standard and it forms the basis for most communication interfaces adopted by parallel computing programmers. The older MPI 1.3 standard (dubbed MPI-1) provides over 115 functions. The later MPI 2.2 standard (or MPI-2) offers over 500 functions and is largely backward compatible with MPI-1. However, not all MPI libraries provide a full implementation of MPI-2. MPI stands for Message Passing Interface. 

            MPI is used to send messages from one process (computer, workstation etc.) to another. These messages can contain data ranging from primitive types (integers, strings and so forth) to actual objects.
            MPI is only an interface, as such you will need an Implementation of MPI before you can start coding. The interface itself lists the functions that any implementation of it must be able to perform.
As such, MPI implementations are standardized on the basis that they all conform to the overarching interface. Think of MPI as a protocol: it defines the rules for Message Passing, but it is up to implementations to implement functions that follow the rules.
            MPI is a language-independent communications protocol. Implementations of MPI have been developed for several different languages.
            For example, pyMPI is used for Python and MPI.NET is used for C#. Note: in this lecture we are using MPI.NET and C#.
            To summarize: MPI is a message passing library whose implementations are used to send messages (data, instructions, etc.) to other processes in order to perform specific tasks. In this way MPI is very much a Distributed topic.

Uses of MPI

• MPI is helpful whenever you need several workstations (or clusters) to work together efficiently and effectively.
• Two examples of such tasks are Parallel Computing and Monte Carlo Simulations.

Q.23} How message passing works

Message Passing:
            It is a mechanism for a process to communicate and synchronize. Using message passing, the process communicates with each other without resorting to shared variables. IPC mechanism provides two operations:

• Send (message)- message size fixed or variable
• Received (message)

            Message passing is the basis of most interprocess communication in distributed systems. It isat the lowest level of abstraction and requires the application programmer to be able to identify the destination process, the message, the source process and the data types expected from these processes.
            Syntax Communication in the message passing paradigm, in its simplest form, is performed using thesend() andreceive() primitives.
            The syntax is generally of the form:send(receiver, message)receive(sender,message)Thesend() primitive requires the name of the destination process and the message data asparameters. The addition of the name of the sender as a parameter for thesend() primitivewould enable the receiver to acknowledge the message. Thereceive()primitive requires the name of the anticipated sender and should provide a storage buffer for the message
            Message passing model allows multiple processes to read and write data to the message queue without being connected to each other. Messages are stored on the queue until their recipient retrieves them. Message queues are quite useful for interprocess communication and are used by most operating systems.

A diagram that demonstrates message passing model of process communication is given as follows −

In the above diagram, both the processes P1 and P2 can access the message queue and store and retrieve data.