Load Balancing Techniques

Q. Short note on : Load Balancing Techniques (December 2018) (10 Marks)

Ans -  There are numerous techniques and algorithms that can be used to intelligently load balance client access requests across server pools. The technique chosen will depend on the type of service or application being served and the status of the network and servers at the time of the request. 

Round Robin
A simple method of load balancing servers. Multiple identical servers are configured to provide the same services. All are configured to use the same Internet domain name, but each has a unique IP address. A DNS server has a list of all the unique IP addresses that are associated with the Internet domain name. When requests for the IP Address associated with the Internet domain name are received, the addresses are returned in a rotating sequential manner.

Weighted Round Robin
Weighted Round Robin builds on the simple Round Robin load balancing method. In the weighted version, each server in the pool is given a static numerical weighting. Servers with higher ratings get more requests sent to them.

Least Connection
Neither Round Robin or Weighted Round Robin take the current server load into consideration when distributing requests. The Least Connection method does take the current server load into consideration. The current request goes to the server that is servicing the least number of active sessions at the current time.

Weighted Least Connection
Builds on the Least Connection method. Like in the Weighted Round Robin method each server is given a numerical value. The load balancer uses this when allocating requests to servers. If two servers have the same number of active connections, then the server with the higher weighting will be allocated the new request.

Agent-Based Adaptive Load Balancing
Each server in the pool has an agent that reports on its current load to the load balancer. This real-time information is used when deciding which server is best placed to handle a request. This is used in conjunction with other techniques such as Weighted Round Robin and Weighted Least Connection.

Chained Failover (Fixed Weighted)
In this method, a predetermined order of servers is configured in a chain. All requests are sent to the first server in the chain. If it can’t accept any more requests the next server in the chain is sent all requests, then the third server. And so on.
 

Weighted Response Time
This method uses the response information from a server health check to determine the server that is responding fastest at a particular time. The next server access request is then sent to that server. This ensures that any servers that are under heavy load, and which will respond more slowly, are not sent new requests. This allows the load to even out on the available server pool over time.

Source IP Hash
This algorithm combines source and destination IP addresses of the client and server to generate a unique hash key. The key is used to allocate the client to a particular server. As the key can be regenerated if the session is broken, the client request is directed to the same server it was using previously. This is useful if it’s important that a client should connect to a session that is still active after a disconnection. For example, to retain items in a shopping cart between sessions.

Global Server Load Balancing (GSLB)
GSLB load balances DNS requests, not traffic. It uses algorithms such as round robin, weighted round robin, fixed weighting, real server load, location-based, proximity and all available. It offers High Availability through multiple data centers. If a primary site is down, traffic is diverted to a disaster recovery site. Clients connect to their fastest performing, geographically closest data center. Application health checking ensures unavailable services or data centers are not visible to clients.

 

An architecture of Distributed Information System

Q. Short note on : An architecture of Distributed Information System. ( December 2018 ) ( 10 Marks )
Ans -

1. Distributed information systems represent an increasingly important trend to computer users. 
2. Distributed processing is a technique for implementing a single logical set of processing functions across a number of physical devices, so that each performs some part of the total processing required. 
3. Distributed processing is often accompanied by the formation of a distributed database. 
4. A distributed database exists when the data elements stored at multiple locations are interrelated, or if a process (program execution) at one location requires access to data stored at another location. 
5. Examples of how these techniques are being used are provided, with comments on the advantages and disadvantages of the distribution of processing and databases in the current state-of-the-art.

Separation of functionality into three conceptual layers

1.  Presentation

• interacts with client

1. present information
2. accept requests
3. graphical user interface, or module that formats/transforms data, or ...

  2. Application logic

1.   programs that implement the services offered by the IS
2.   often retrieves/modifies data

 3. Resource management

• manages the data sources of the IS

1.  DBMSs
2. file system
3. any "external" systemn

Discuss Ricart–Agrawala algorithm and justify how this algorithm optimize message overhead in achieving mutual exclusion.

Q. Discuss Ricart–Agrawala algorithm and justify how this algorithm optimize message overhead in achieving mutual exclusion. (December 2018) (10 Marks)

Ans -  

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:

1. Two type of messages ( REQUEST and REPLY) are used and communication channels are assumed to follow FIFO order.
2. A site send a REQUEST message to all other site to get their permission to enter critical section.
3. A site send a REPLY message to other site to give its permission to enter the critical section.
4. A timestamp is given to each critical section request using Lamport’s logical clock.
5. 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 S_i wants to enter the critical section, it send a timestamped REQUEST message to all other sites.
  • When a site S_j receives a REQUEST message from site S_i, It sends a REPLY message to site S_i if and only if
    • Site S_j is neither requesting nor currently executing the critical section.
    • In case Site S_j is requesting, the timestamp of Site S_i‘s request is smaller than its own request.
    Otherwise the request is deferred by site S_j.
• To execute the critical section:
  • Site S_i enters the critical section if it has received the REPLY message from all other sites.
• To release the critical section:
  • Upon exiting site S_i 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

• (N – 1) request messages
• (N – 1) reply messages

Performance:

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

Discuss and differentiate different client-centric consistency models by providing suitable example

Q. Discuss and differentiate different client-centric consistency models by providing suitable example. (December 2018) (10 Marks).

Ans -  Consistency Model

1. A consistency model is contract between a distributed data store and processes, in which the processes agree to obey certain rules in contrast the store promises to work correctly.
2. A consistency model basically refers to the degree of consistency that should be maintained for the shared memory data.
3. If a system supports the stronger consistency model, then the weaker consistency model is automatically supported but the converse is not true.

Client-centric

• Client-centric consistency models aim at providing a system wide view on a data store.This model concentrates on consistency from the perspective of a single mobile client.
• Client-centric consistency models are generally used for applications that lack simultaneous updates were most operations involve reading data.

i.Eventual Consistency

• In Systems that tolerate high degree of inconsistency, if no updates take place for a long time all replicas will gradually and eventually become consistent. This form of consistency is called eventual consistency.
• Eventual consistency only requires those updates that guarantee propagation to all replicas.
• Eventual consistent data stores work fine as long as clients always access the same replica.
• Write conflicts are often relatively easy to solve when assuming that only a small group of processes can perform updates. Eventual consistency is therefore often cheap to implement.

ii.Monotonic Reads Consistency 

• A data store is said to provide monotonic-read consistency if a process reads the value of a data item x, any successive read operation on x by that process will always return that same value or a more recent value.
• A process has seen a value of x at time t, it will never see an older version of x at a later time.
• Example: A user can read incoming mail while moving. Each time the user connects to a different e-mail server, that server fetches all the updates from the server that the user previously visited. Monotonic Reads guarantees that the user sees all updates, no matter from which server the automatic reading takes place.

iii.Monotonic Writes

• A data store is said to be monotonic-write consistent if a write operation by a process on a data item x is completed before any successive write operation on X by the same process.
• A write operation on a copy of data item x is performed only if that copy has been brought up to date by means of any preceding write operations, which may have taken place on other copies of x.
• Example: Monotonic-write consistency guarantees that if an update is performed on a copy of Server S, all preceding updates will be performed first. The resulting server will then indeed become the most recent version and will include all updates that have led to previous versions of the server.

iv.Read Your Writes

• A data store is said to provide read-your-writes consistency if the effect of a write operation by a process on data item x will always be a successive read operation on x by the same process.
• A write operation is always completed before a successive read operation by the same process no matter where that read operation takes place.
• Example: Updating a Web page and guaranteeing that the Web browser shows the newest version instead of its cached copy.

v.Writes Follow Reads

• A data store is said to provide writes-follow-reads consistency if a process has write operation on a data item x following a previous read operation on x then it is guaranteed to take place on the same or a more recent value of x that was read.
• Any successive write operation by a process on a data item x will be performed on a copy of x that is up to date with the value most recently read by that process.
• Example: Suppose a user first reads an article A then posts a response B. By requiring writes-follow-reads consistency, B will be written to any copy only after A has been written.

What is the need of process migration and explain the role of resource to process and process to resource binding in process migration.

Q. What is the need of process migration and explain the role of resource to process and process to resource binding in process migration. (December 2018) (10 Marks)

Ans- 

• In computing, process migration is a specialized form of process management whereby processes are moved from one computing environment to another. This originated in distributed computing, but is now used more widely. On multi core machines (multiple cores on one processor or multiple processors) process migration happens as a standard part of process scheduling, and it is quite easy to migrate a process within a given machine, since most resources (memory, files, sockets) do not need to be changed, only the execution context (primarily program counter and registers).
• The traditional form of process migration is in computer clusters where processes are moved from machine to machine, which is significantly more difficult, as it requires serializing the process image and migrating or reacquiring resources at the new machine

Need of Process Migration

Dynamic  Load  Balancing : It  allows  processes  to  take  advantage  of  less  loaded  2 nodes by migrating from overloaded ones.

Availability : Processes  reside  on  a  failure  node  can  be  migrated  to  other  healthy  nodes. 

System Administration : Processes  that  reside  on  a  node  that  is  to  be  undergone  system maintenance can be migrated to other nodes. 

Data  Locality : Processes  can  take  advantage  of  locality  of  data  or  other  special  capabilities of a particular node. 

Mobility : Processes can be migrated from a handheld device or laptop computer to a  more  powerful  server  computer  before  the  device  get  disconnected  from  the  network.  

Fault Recovery : The  mechanism  to  halt,  transport  and  resume  a  process  is  technically  useful  to  support  fault  recovery  in  mission-critical  or  transaction-based  applications. 

A process involves code segment + resources segment + execution segment.

Binding can be initiated by sender or receiver.

In sender initiated code is with sender sends a query to data server is an example of sender initiated in which process binds to resource.

In receiver initiated : Receiver gets process migrated on demand.

Describe any one method of Logical Clock synchronization with the help of an example.

Q.Describe any one method of Logical Clock synchronization with the help of an example. (December 2018 ) (10 Marks)

Ans- The concept of time in distributed systems is used to order events. The assumption is that the execution of a process is characterized by a sequence of events. An event can be the execution at one instruction or of one procedure or sending a message or receiving a message. Under some condition it is possible to ascertain the order of the events logical clocks try to catch this.

 

Logical clocks :

The happened before relation ( →) is defined as follows :

• A→B if A & B are within the same process & A occurred before B.
• A→B if A is an event at sending messages in one process end B is the event of receiving M in another process. 
• A→B and B→C then A→C
  Event A causally affects event B if A→Bdistinct events A & B are ( A || B) if we do not have A→B or B→A
  

Example:

 

Differentiate between Message oriented & Stream oriented communications.

Q.Differentiate between Message oriented & Stream oriented communications.
 (December 2018) (10 Marks)
Ans -

Table : Difference between Message-Oriented & Stream Oriented Communication

What are various sytem models of distributed system.

Q. What are various sytem models of distributed system. (December 2018) (10 Marks)

Ans - Distributed Computing system models can be broadly classified into five categories. They are

1. Minicomputer model
2. Workstation model
3. Workstation – server model
4. Processor – pool model
5. Hybrid model

Minicomputer Model
The minicomputer model  is a simple extension of the centralized time-sharing system. A distributed computing system based on this model consists of a few minicomputers (they may be large supercomputers as well) interconnected by a communication network. Each minicomputer usually has multiple users simultaneously logged on to it. For this, several interactive terminals are connected to each minicomputer. Each user is logged on to one specific minicomputer, with remote access to other minicomputers. The network allows a user to access remote resources that are available on some machine other than the one on to which the user is currently logged. The minicomputer model may be used when resource sharing (such as sharing of information databases of different types, with each type of database located on a different machine) with remote users is desired. The early ARPAnet is an example of a distributed computing system based on the minicomputer model.

Workstation Model

A distributed computing system based on the workstation model consists of several workstations interconnected by a communication network. An organization may have several workstations located throughout a building or campus, each workstation equipped with its own disk and serving as a single-user computer. It has been often found that in such an environment, at any one time a significant proportion of the workstations are idle (not being used), resulting in the waste of large amounts of CPU time. Therefore, the idea of the workstation model is to interconnect all these workstations by a high-speed LAN so that idle workstations may be used to process jobs of users who are logged onto other workstations and do not have sufficient processing power at their own workstations to get their jobs processed efficiently.  

Workstation – Server Model
The workstation model is a network of personal workstations, each with its own disk and a local file system. A workstation with its own local disk is usually called a diskful workstation and a workstation without a local disk is called a diskless workstation. With the proliferation of high-speed networks, diskless workstations have become more popular in network environments than diskful workstations, making the workstation-server model more popular than the workstation model for building distributed computing systems.A distributed computing system based on the workstation-server model consists of a few minicomputers and several workstations (most of which are diskless, but a few of which may be diskful) interconnected by a communication network.

Processor – Pool Model
The processor-pool model is based on the observation that most of the time a user does not need any computing power but once in a while the user may need a very large amount of computing power for a short time (e.g., when recompiling a program consisting of a large number of files after changing a basic shared declaration). Therefore, unlike the workstation-server model in which a processor is allocated to each user, in the processor-pool model the processors are pooled together to be shared by the users as needed. The pool of processors consists of a large number of microcomputers and minicomputers attached to the network. Each processor in the pool has its own memory to load and run a system program or an application program of the distributed computing system

Hybrid Model
Out of the four models described above, the workstation-server model, is the most widely used model for building distributed computing systems. This is because a large number of computer users only perform simple interactive tasks such as editing jobs, sending electronic mails, and executing small programs. The workstation-server model is ideal for such simple usage. However, in a working environment that has groups of users who often perform jobs needing massive computation, the processor-pool model is more attractive and suitable.

What are the desirable feature a good distributed file system? Explain file sharing semantics for it.

Q. What are the desirable feature a good distributed file system? Explain file sharing semantics for it. (May 16) (10 Marks)

Ans - A good distributed file system should have the following features:

1.Transparency

Transparency refers to hiding details from a user.The following types of transparency are desirable.

i. Structure transparency:Multiple file servers are used to provide better performance,scalability,& reliability.The multiplicity of file servers should be transparent to the client of a distributed file system.Clients should not know the number or locations of file servers or the storage devices instead it should look like a conventional file system offered by a centralized,time sharing operating system.

ii.Access transparency: Local and remote files should be accessible in the same way. The file system should automatically locate an accessed file and transport it to the client’s site.

iii.Naming transparency: The name of the file should not reveal the location of the file. The name of the file must not be changed while moving from one node to another.

iv.Replication transparency: The existence of multiple copies and their locations should be hidden from the clients where files are replicated on multiple nodes.

2.User mobility

The user should not be forced to work on a specific node but should have the flexibility to work on different nodes at different times. This can be achieved by automatically bringing the users environment to the node where the user logs in.

3.Performance

Performance is measured as the average amount of time needed to satisfy client requests, which includes CPU time plus the time for accessing secondary storage along with network access time. Explicit file placement decisions should not be needed to increase the performance of a distributed file system.

4.Simplicity and ease of use

User interface to the file system be simple and number of commands should be as small as possible. A DFS should be able to support the whole range of applications.

5.Scalability

A good DFS should cope with an increase of nodes and not cause any disruption of service. Scalability also includes the system to withstand high service load, accommodate growth of users and integration of resources.

6.High availability

A distributed file system should continue to function even in partial failures such as a link failure, a node failure, or a storage device crash. Replicating files at multiple servers can help achieve availability.

7.High reliability
 Probability of loss of stored data should be minimized. System should automatically generate backup copies of critical files in event of loss.

8.Data integrity

Concurrent access requests from multiple users who are competing to access the file must be properly synchronized by the use of some form of concurrency control mechanism. Atomic transactions can also be provided to users by a file system for data integrity.

9.Security

A distributed file system must secure data so that its users are confident of their privacy. File system should implement mechanisms to protect data that is stored within.

10.Heterogeneity

Distributed file system should allow various types of workstations to participate in sharing files via distributed file system. Integration of a new type of workstation or storage media should be designed by a DFS.

File-sharing semantics
Multiple users may access a shared file simultaneously. An important design issue for any file system is to define when modifications of file data done by a user are visible to other users. This is defined by the file-sharing semantics used by the file system.

1. UNIX semantics
Absolute time ordering is enforced on operations which ensure that read operation on a file sees the effects of all previous write operations performed on that file. Write to an open file immediately become visible to users accessing the file at the same time.

2. Session semantics
A session is a series of file accesses made between the open and close file operations. The changes made to a file are made visible only to the client process that opened the session and is made invisible to the other remote processes that have the same file open simultaneously. The changes made to the file are available to the remote processes only after the session is closed.

3. Immutable shared-files semantics

This is based on the use of immutable file model where an immutable file cannot be modified once it is created. Changes to the file are handled by creating a new updated version of the file. The semantics allows the file to be shared only in the read-only mode. With this approach, shared files cannot be shared at all.

4. Transaction-like semantics 

This is based on the use of transaction mechanism which ensures that partial changes made to the shared data by a transaction will not be visible to other concurrently executing transactions until the transaction ends.

Andrew File System(AFS)

Q. Short Note on Andrew File System(AFS) (December 16) (10 Marks)

Ans -

1. Distributed network file system which uses a set of trusted servers to present a homogeneous, location transparent file name space to all the client workstation
2. Distributed computing environment developed at Carnegie Mellon University (CMU) for use as a campus computing and information system [Morris et al. 1986].
3. Intention is to support information sharing on a large scale by minimizing client-server communication
4. Achieved by transferring whole files between server and client computers and caching them at clients until the servers receives a more up-to-date version.

Features of AFS

• Uniform namespace
• Location-independent file sharing
• Client-side caching
• Secure authentication
• Replication
• Whole-file serving
• Whole-file caching

Working

Implemented as 2 software components that exists as UNIX processes called Vice and Venus

Vice: Name given to the server software that runs as a user level UNIX process in each server computer.

Venus: User level process that runs in each client computer and corresponds to the client module in our abstract model. Files available to user are either local or shared

Local files are stored on a workstation's disk and are available only to local user processes.

Shared files are stored on servers, copies of them are cached on the local disk of work stations.

Explain distributed algorithm for mutual exclusion. What are the advantages and disadvantage of it over centralized algorithm.

Q. Explain distributed algorithm for mutual exclusion. What are the advantages and disadvantage of it over centralized algorithm. (May 16) (10 Marks)

Ans-  

1. 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.
2. In Distributed systems, we neither have shared memory nor a common physical clock and there for we can not solve mutual exclusion problem using shared variables. To eliminate the mutual exclusion problem in distributed system approach based on message passing is used.

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:

1. 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.
   • This approach insures Mutual exclusion as the token is unique

   • Example: 
     Suzuki-Kasami’s Broadcast Algorithm

2. 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.
   • All algorithm which follows non-token based approach maintains a logical clock. Logical clocks get updated according to Lamport’s scheme

   • Example: 
     Lamport's algorithm, Ricart–Agrawala algorithm

3. 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

   • Example: 
     Maekawa’s Algorithm

What are different models of middleware?

Q. What are different models of middleware ? (May 16) (10 Marks)

Ans -  

RPCs (Remote Procedure Call) Middleware

RPC exists since the 1970s and are the oldest type of middleware and it is client/server based. One client can request a service from a program located in another computer in a network without having to understand network details. RPCs are synchronous; they are labelled as “blocking middleware” because the requesting program is suspended until the results of the remote procedure are returned. As the RPC’s use a point-to-point communication, they are not scalable and consume a vast amount of resources during they processing . Despite the simplicity, the complexity of their maintenance and performance issues, make this middleware not a viable solution in scenarios where there are many applications requiring integration.
 

MOM (Message Oriented Middleware)

MOM is a type of middleware that uses messages as the method of integration. In MOM the applications are decoupled. Sender and receivers are never aware of each other; instead they send and receive the messages from the messaging system. It is the responsibility of the MOM to get the messages to their destinations . The messaging system uses channels that the applications can recognize and the messages can be sent and received asynchronously. The asynchronous paradigm allows the application to continue functioning after sending a request, so if the message is taking too much time it is possible to process other messages while is waiting, they can deal with down connections and queue messages until it’s viable to deliver them . One established standard is the JMS (Java Message Service), which provides an API and a set of rules that govern message delivery.

 

Distributed Objects

Distributed objects are small applications that use standard interfaces and protocols to communicate with one another. Because they are built over standards, two compliant objects should be able to exchange information and carry out application functions by invoking each other methods.Two important distributed objects specifications exist, CORBA (Common Object Request Broker Architecture) and DCOM (Distributed Component Object Model). CORBA is an architecture and specification for creating, distributing, and managing distributed objects in a network. It allows different objects at different locations to communicate through an interface broker. CORBA uses the ORB (Object Request Broker). ORB allows an object to request services from other object without having to learn his location in a distributed network using the CORBA Interface repository to locate and communicate with a requested object. To enable interoperability between different ORBs, the GIOP (General Inter-ORB Protocol) and for the Internet, the IIOP Internet Inter-ORB Protocol) were implemented, both over TCP/IP .DCOM (Distributed Component Object Model) is the Microsoft equivalent to CORBA. It is based on the DOM (Component Object Model) and provides a set of concepts and interfaces that allows client objects request services from server objects in a network. DCOM allows bridging with CORBA, mapping COM objects to appear as CORBA objects.

 

Database Middleware

Database middleware allows communications with a database from an application or between databases. It is used to extract information from either local or remote databases. It works with two database types, CLIs (Call level interfaces) and at-native database middleware. CLIs provide access to any number of relational databases through a common interface. On the other way, native database middleware uses the features and functions of a particular data base, using only native mechanisms. Although only communicate with one database, it has as advantages, improved performance and access to all low features of a particular type of databases.

Transaction Processing Monitors

They are a type of middleware that preserves the integrity of a transaction. TP Monitors support features such rollback, failover, auto restart, error logging and replication to eliminate single points of failure. They provide a location for application logic in addition to communication between two or more applications.

Message Brokers

Message Brokers allow the information flow between applications. They can, regardless the type of application, join them using common rules and routing engines.

 

 

Write Suzuki-Kasmi's Broadcast algorithm. Explain with example.

Q. Write Suzuki-Kasmi's Broadcast algorithm. Explain with example.(May 16 ) (10 Marks)

Ans - Suzuki–Kasami algorithm is a token-based algorithm for achieving mutual exclusion in distributed systems.This is modification of Ricart–Agrawala algorithm, a permission based (Non-token based) algorithm which uses REQUEST and REPLY messages to ensure mutual exclusion.

In token-based algorithms, A site is allowed to enter its critical section if it possesses the unique token. Non-token based algorithms uses timestamp to order requests for the critical section where as sequence number is used in token based algorithms.

Each requests for critical section contains a sequence number. This sequence number is used to distinguish old and current requests.

Data structure and Notations:

• An array of integers RN[1…N]
  A site S_i keeps RN_i[1…N], where RN_i[j] is the largest sequence number received so far through REQUEST message from site S_i.
• An array of integer LN[1…N]
  This array is used by the token.LN[J] is the sequence number of the request that is recently executed by site S_j.
• A queue Q
  This data structure is used by the token to keep record of ID of sites waiting for the token

Algorithm:

• To enter Critical section:
  • When a site S_i wants to enter the critical section and it does not have the token then it increments its sequence number RN_i[i] and sends a request message REQUEST(i, sn) to all other sites in order to request the token.
    Here sn is update value of RN_i[i]
  • When a site S_j receives the request message REQUEST(i, sn) from site S_i, it sets RN_j[i] to maximum of RN_j[i] and sn i.e RN_j[i] = max(RN_j[i], sn).
  • After updating RN_j[i], Site S_j sends the token to site S_i if it has token and RN_j[i] = LN[i] + 1
• To execute the critical section:
  • Site S_i executes the critical section if it has acquired the token.
• To release the critical section:
  After finishing the execution Site S_i exits the critical section and does following:
  • sets LN[i] = RN_i[i] to indicate that its critical section request RN_i[i] has been executed
  • For every site S_j, whose ID is not prsent in the token queue Q, it appends its ID to Q if RN_i[j] = LN[j] + 1 to indicate that site S_j has an outstanding request.
  • After above updation, if the Queue Q is non-empty, it pops a site ID from the Q and sends the token to site indicated by popped ID.
  • If the queue Q is empty, it keeps the token 
  
  
  

Explain File Access Models. (December 2017) (10 Marks).

Q. Explain File Access Models. (December 2017) (10 Marks ).

Ans - The specific client's request for accessing a particular file is serviced on the basis of the file accessing model used by the distributed file system.The file accessing model basically depends on 

1. the unit of data access and 
2. the method used for accessing remote files.

On the basis of the unit of data access, following file access models might be used in order to access the specific file.

1.     File-level transfer model
2.     Block-level transfer model
3.     Byte-level transfer model
4.     Record-level transfer model

1.File-level transfer model: In file-level transfer model, the complete file is moved while a particular operation necessitates the file data to be transmitted all the way through the distributed computing network amongst client and server. This model has better scalability and is efficient.

2.Block-level transfer model: In block-level transfer model, file data transfers through the network amongst client and a server is accomplished in units of file blocks. In short, the unit of data transfer in block-level transfer model is file blocks. The block-level transfer model might be used in distributed computing environment comprising several diskless workstations.

3.Byte-level transfer model: In byte-level transfer model, file data transfers the network amongst client and a server is accomplished in units of bytes. In short, the unit of data transfer in byte-level transfer model is bytes. The byte-level transfer model offers more flexibility in comparison to the other file transfer models since, it allows retrieval and storage of an arbitrary sequential subrange of a file. The major disadvantage of byte-level transfer model is the trouble in cache management because of the variable-length data for different access requests.

4.Record-level transfer model: The record-level file transfer model might be used in the file models where the file contents are structured in the form of records. In record-level transfer model, file data transfers through the network amongst client and a server is accomplished in units of records. The unit of data transfer in record-level transfer model is record.