Monday 2 May 2011

Distributed Systems: Concepts and Design By George Coulouris - Exercise Solutions

Edition 3
By George Coulouris, Jean Dollimore and Tim Kindberg
Addison-Wesley, ©Pearson Education 2001


1.9 Suppose that the operations of the BLOB object are separated into two categories – public
operations that are available to all users and protected operations that are available only to certain
named users. State all of the problems involved in ensuring that only the named users can use a
protected operation. Supposing that access to a protected operation provides information that
should not be revealed to all users, what further problems arise?

1.9 - Answer

Each request to access a protected operation must include the identity of the user making the request. The
problems are:
• defining the identities of the users. Using these identities in the list of users who are allowed to access
the protected operations at the implementation of the BLOB object. And in the request messages.
• ensuring that the identity supplied comes from the user it purports to be and not some other user
pretending to be that user.
• preventing other users from replaying or tampering with the request messages of legitimate users.
Further problems.
• the information returned as the result of a protected operation must be hidden from unauthorised users.
This means that the messages containing the information must be encrypted in case they are intercepted
by unauthorised users.

1.10 - The INFO service manages a potentially very large set of resources, each of which can be accessed
by users throughout the Internet by means of a key (a string name). Discuss an approach to the
design of the names of the resources that achieves the minimum loss of performance as the number
of resources in the service increases. Suggest how the INFO service can be implemented so as to
avoid performance bottlenecks when the number of users becomes very large.

1.10 - Answer

Algorithms that use hierarchic structures scale better than those that use linear structures. Therefore the
solution should suggest a hierarchic naming scheme. e.g. that each resource has an name of the form ’A.B.C’
etc. where the time taken is O(log n) where there are n resources in the system.
To allow for large numbers of users, the resources are partitioned amongst several servers, e.g. names
starting with A at server 1, with B at server 2 and so forth. There could be more than one level of partitioning
as in DNS. To avoid performance bottlenecks the algorithm for looking up a name must be decentralised. That
is, the same server must not be involved in looking up every name. (A centralised solution would use a single
root server that holds a location database that maps parts of the information onto particular servers). Some
replication is required to avoid such centralisation. For example: i) the location database might be replicated at multiple root servers or ii) the location database might be replicated in every server. In both cases, different
clients must access different servers (e.g. local ones or randomly).

1.11 - List the three main software components that may fail when a client process invokes a method in
a server object, giving an example of a failure in each case. To what extent are these failures
independent of one another? Suggest how the components can be made to tolerate one another’s
failures.
1.11 - Answer

The three main software components that may fail are:
• the client process e.g. it may crash
• the server process e.g. the process may crash
• the communication software e.g. a message may fail to arrive
The failures are generally caused independently of one another. Examples of dependent failures:
• if the loss of a message causes the client or server process to crash. (The crashing of a server would cause
a client to perceive that a reply message is missing and might indirectly cause it to fail).
• if clients crashing cause servers problems.
• if the crash of a process causes a failures in the communication software.
Both processes should be able to tolerate missing messages. The client must tolerate a missing reply message
after it has sent an invocation request message. Instead of making the user wait forever for the reply, a client
process could use a timeout and then tell the user it has not been able to contact the server.
A simple server just waits for request messages, executes invocations and sends replies. It should be
absolutely immune to lost messages. But if a server stores information about its clients it might eventually fail
if clients crash without informing the server (so that it can remove redundant information). (See stateless
servers in chapter 4/5/8).
The communication software should be designed to tolerate crashes in the communicating processes.
For example, the failure of one process should not cause problems in the communication between the surviving
processes.
1.12 - A server process maintains a shared information object such as the BLOB object of Exercise 1.7.
Give arguments for and against allowing the client requests to be executed concurrently by the
server. In the case that they are executed concurrently, give an example of possible ‘interference’
that can occur between the operations of different clients. Suggest how such interference may be
prevented.
1.12 - Answer
 For concurrent executions - more throughput in the server (particularly if the server has to access a disk or
another service)
Against - problems of interference between concurrent operations
Example:
Client A’s thread reads value of variable X
Client B’s thread reads value of variable X
Client A’s thread adds 1 to its value and stores the result in X
Client B’s thread subtracts 1 from its value and stores the result in X
Result: X := X-1; imagine that X is the balance of a bank account, and clients A and B are implementing credit
and debit transactions, and you can see immediately that the result is incorrect.
To overcome interference use some form of concurrency control. For example, for a Java server use
synchronized operations such as credit and debit.

1.13 - A service is implemented by several servers. Explain why resources might be transferred between
them. Would it be satisfactory for clients to multicast all requests to the group of servers as a way
of achieving mobility transparency for clients?
1.13 - Answer

Migration of resources (information objects) is performed: to reduce communication delays (place objects in
a server that is on the same local network as their most frequent users); to balance the load of processing and
or storage utilisation between different servers.
If all servers receive all requests, the communication load on the network is much increased and servers must
do unnecessary work filtering out requests for objects that they do not hold.

If you found the answer useful, please visit my other website. Exercise or Fitness Training has huge psychological and physical benefits. Train and dress up for the occasion.

12 comments: