Distributed Systems: Concepts and Design. by George Coulouris. Exercise Solutions 2

Edition 3

By George Coulouris, Jean Dollimore and Tim Kindberg

Addison-Wesley, ©Pearson Education 2001

Chapter 1 Exercise Solutions

1.2 How might the clocks in two computers that are linked by a local network be synchronized without

reference to an external time source? What factors limit the accuracy of the procedure you have

described? How could the clocks in a large number of computers connected by the Internet be

synchronized? Discuss the accuracy of that procedure.

1.2 Answer

Several time synchronization protocols are described in Section 10.3. One of these is Cristian’s protocol.

Briefly, the round trip time t to send a message and a reply between computer A and computer B is measured

by repeated tests; then computer A sends its clock setting T to computer B. B sets its clock to T+t/2. The setting

can be refined by repetition. The procedure is subject to inaccuracy because of contention for the use of the

local network from other computers and delays in the processing the messages in the operating systems of A

and B. For a local network, the accuracy is probably within 1 ms.

For a large number of computers, one computer should be nominated to act as the time server and it

should carry out Cristian’s protocol with all of them. The protocol can be initiated by each in turn. Additional

inaccuracies arise in the Internet because messages are delayed as they pass through switches in wider area

networks. For a wide area network the accuracy is probably within 5-10 ms. These answers do not take into

account the need for fault-tolerance. See Chapter 10 for further details.

1.3 A user arrives at a railway station that she has never visited before, carrying a PDA that is capable

of wireless networking. Suggest how the user could be provided with information about the local

services and amenities at that station, without entering the station’s name or attributes. What

technical challenges must be overcome?

1.3 Answer

The user must be able to acquire the address of locally relevant information as automatically as possible. One

method is for the local wireless network to provide the URL of web pages about the locality over a local

wireless network.

For this to work: (1) the user must run a program on her device that listens for these URLs, and which gives

the user sufficient control that she is not swamped by unwanted URLs of the places she passes through; and

(2) the means of propagating the URL (e.g. infrared or an 802.11 wireless LAN) should have a reach that

corresponds to the physical spread of the place itself.

1.4 What are the advantages and disadvantages of HTML, URLs and HTTP as core technologies for

information browsing? Are any of these technologies suitable as a basis for client-server

computing in general?

1.4 Answer

HTML is a relatively straightforward language to parse and render but it confuses presentation with the

underlying data that is being presented.

URLs are efficient resource locators but they are not sufficiently rich as resource links. For example, they may

point at a resource that has been relocated or destroyed; their granularity (a whole resource) is too coarsegrained

for many purposes.

HTTP is a simple protocol that can be implemented with a small footprint, and which can be put to use in many

types of content transfer and other types of service. Its verbosity (HTML messages tend to contain many

strings) makes it inefficient for passing small amounts of data.

HTTP and URLs are acceptable as a basis for client-server computing except that (a) there is no strong typechecking

(web services operate by-value type checking without compiler support), (b) there is the inefficiency

that we have mentioned.

1.5 Use the World Wide Web as an example to illustrate the concept of resource sharing, client and

server.

Resources in the World Wide Web and other services are named by URLs. What do the initials URL denote? Give examples of three different sorts of web resources that can be named by URLs.

1.5 Answer

Web Pages are examples of resources that are shared. These resources are managed by Web servers.

Client-server architecture. The Web Browser is a client program (e.g. Netscape) that runs on the user's

computer. The Web server accesses local files containing the Web pages and then supplies them to client

browser processes.

URL - Uniform Resource Locator

(3 of the following a file or a image, movies, sound, anything that can be rendered, a query to a database or to

a search engine.

1.6 Give an example of a URL.

List the three main components of a URL, stating how their boundaries are denoted and illustrating

each one from your example.

To what extent is a URL location transparent?

1.6 Answer

• The protocol to use. the part before the colon, in the example the protocol to use is http ("HyperText

Transport Protocol").

• The part between // and / is the Domain name of the Web server host www.dcs.qmw.ac.uk.

• The remainder refers to information on that host - named within the top level directory used by that Web

server research/distrib/book.html.

The hostname www is location independent so we have location transparency in that the address

of a particular computer is not included. Therefore the organisation may move the Web service to

another computer.

But if the responsibility for providing a WWW-based information service moves to another

organisation, the URL would need to be changed.

1.7 A server program written in one language (for example C++) provides the implementation of a

BLOB object that is intended to be accessed by clients that may be written in a different language

(for example Java). The client and server computers may have different hardware, but all of them

are attached to an internet. Describe the problems due to each of the five aspects of heterogeneity

that need to be solved to make it possible for a client object to invoke a method on the server

object.

1.7 Answer

As the computers are attached to an internet, we can assume that Internet protocols deal with differences in

networks.

But the computers may have different hardware - therefore we have to deal with differences of

representation of data items in request and reply messages from clients to objects. A common standard will be

defined for each type of data item that must be transmitted between the object and its clients.

The computers may run different operating systems, therefore we need to deal with different operations

to send and receive messages or to express invocations. Thus at the Java/C++ level a common operation would

be used which will be translated to the particular operation according to the operating system it runs on.

We have two different programming languages C++ and Java, they use different representations for data

structures such as strings, arrays, records. A common standard will be defined for each type of data structure

that must be transmitted between the object and its clients and a way of translating between that data structure

and each of the languages.

We may have different implementors, e.g. one for C++ and the other for Java. They will need to agree

on the common standards mentioned above and to document them.

1.8 An open distributed system allows new resource sharing services such as the BLOB object in

Exercise 1.7 to be added and accessed by a variety of client programs. Discuss in the context of

this example, to what extent the needs of openness differ from those of heterogeneity.

1.8 Answer

To add the BLOB object to an existing open distributed system, the standards mentioned in the answer to

Exercise 1.7 must already have been agreed for the distributed system To list them again:

• the distributed system uses a common set of communication protocols (probably Internet protocols).

• it uses an defined standard for representing data items (to deal with heterogeneity of hardware).

• It uses a common standard for message passing operations (or for invocations).

• It uses a language independent standard for representing data structures.

But for the open distributed system the standards must have been agreed and documented before the BLOB

object was implemented. The implementors must conform to those standards. In addition, the interface to the

BLOB object must be published so that when it is added to the system, both existing and new clients will be

able to access it. The publication of the standards allows parts of the system to be implemented by different

vendors and to work together.