GTU 3170719 Distributed System (DS) Summer 2026 Solved Paper & Solutions

Three examples of distributed systems are:

1. World Wide Web: web servers all over the world store pages, and a browser reaches them as if they were one large system.
2. Banking and ATM network: the branch servers, ATMs and the central server work together, so that a customer can withdraw money from any ATM.
3. Online ticket booking (such as railway reservation): many servers and databases share the seat data, and thousands of users book tickets at the same time.

Other examples are cloud storage, email, and multiplayer online games.

A distributed system is a collection of independent computers that appears to its users as a single coherent system. The computers are connected by a network and work together by passing messages.

Advantages:

• Resource sharing: printers, files and data can be shared by many users.
• Reliability: if one computer fails, the others keep working, so the whole system does not stop.
• Scalability: more computers can be added when the load grows.
• Speed: a job is divided among many computers and finished faster.

Disadvantages:

• Complexity: the software is harder to design, build and debug.
• Security: data moves over the network, so it can be attacked and stolen more easily.
• Network dependence: if the network is slow or fails, the system suffers.

The main characteristics of a distributed system are listed below.

Example

In an online shopping system, the product data is on many servers (resource sharing, scalability). A customer sees one site (transparency). If one server fails, another gives the data (fault tolerance). Many customers buy at once (concurrency).

Fault tolerance is the ability of a system to continue to work correctly even when some of its components fail.

It is used in distributed systems because there are many computers and network links, so a failure somewhere is common and cannot be avoided. Fault tolerance gives high availability and reliability, so that users still get the service. It is achieved with redundancy (a spare copy of data or a spare server), replication and checkpointing.

Firewall: a firewall is a security system placed between a trusted private network and an untrusted network, such as the Internet. It checks every packet that enters or leaves, against a set of rules, and allows or blocks it.

• A packet filter checks the addresses and the port numbers.
• An application gateway (proxy) checks the data of a particular application.

Denial of Service (DoS): a DoS attack makes a service unavailable to the real users. The attacker floods the server with so many requests that it cannot answer the others.

• In a Distributed DoS (DDoS), the requests come from thousands of infected computers.
• It is reduced by firewalls, limits on the request rate, and extra servers.

Remote Procedure Call (RPC) lets a program call a procedure that runs on another computer, as if it were a local call. The programmer does not write the network code.

How an RPC works

1. The client calls the procedure. The call goes to the client stub.
2. The client stub marshals the parameters, which means that it packs them into a message, and sends it.
3. The message goes through the network to the server. The server stub unpacks (unmarshals) it, and calls the real procedure.
4. The procedure runs, and its result goes back to the server stub.
5. The server stub packs the result and sends it back. The client stub unpacks it and returns it to the caller.

Implementation

1. Write the interface of the remote procedures, in an interface definition language (IDL).
2. A compiler generates the client stub and the server stub from it.
3. The server registers its procedures, and the client binds to the server, using the name or the address.
4. The RPC system handles the transport, the data format and the errors, such as a lost message.

Example

A client calls $add(3, 4)$ on a server. This is a working program using the XML-RPC library of Python:

The output is 7. The object p works as the client stub.

Structured naming: a name that is a path in a hierarchy, such as a domain name www.example.com or a file path /home/user/a.txt. The system finds the entity by following the names, step by step, through the name spaces.

Attribute-based naming: an entity is described by a set of (attribute, value) pairs, and it is found by a search on these. Example: find a printer where type is laser and floor is 2. Directory services, such as LDAP, use it. It is useful when the user does not know the exact name.

Scalability is the ability of a distributed system to keep working well when the number of users, the number of resources, or the area of the system grows.

There are three dimensions:

• Size: more users and resources, with no drop in speed.
• Geographical: the nodes are spread over a large distance, so the delay is longer.
• Administrative: the system spans many organisations with different rules.

Techniques to get scalability are distribution (spreading the work and the data), replication and caching.

Example: the Domain Name System (DNS) divides the name space among many servers, and caches the answers. So billions of requests are handled, and the system works as the Internet grows.

Transparency means that the system hides the fact that its parts and resources are spread over many computers. The user sees one single system. The types are given below.

Two more are sometimes listed: persistence transparency, which hides whether a resource is in the memory or on a disk, and performance transparency, which lets the system adjust to the load.

Full transparency is not always possible. Network delays cannot be hidden fully, and a high level of transparency costs performance.

Virtualization is the creation of a virtual version of a resource, such as a computer, a storage device or a network. A software layer called a hypervisor lets many virtual machines (VMs), each with its own operating system, run on one physical computer.

Uses: better use of hardware, lower cost, isolation of the applications from each other, easy backup and moving of VMs, and quick set up of servers. It is the base of cloud computing.

Code migration is the movement of a program (its code, and sometimes its execution state and data) from one machine to another, so that it runs there.

It is of two kinds. In weak mobility, only the code moves, and it starts afresh. In strong mobility, the running state moves too, and the program continues from where it was.

It is used:

• To balance the load, by moving a process from a busy machine to an idle one.
• To reduce the network traffic, by moving the code to the place where the large data is, instead of moving the data.
• For flexibility, as in a web browser that downloads and runs a script.
• To support a mobile user or device.

The Bully algorithm is used for election of a coordinator among the processes of a distributed system. Every process has a unique number (ID), and the process with the highest ID becomes the coordinator.

Steps

1. A process $P$ finds that the coordinator is not responding, and starts an election.
2. $P$ sends an ELECTION message to all the processes with a higher ID.
3. If no one replies, $P$ wins. It sends a COORDINATOR message to all the others.
4. If a higher process replies with OK, $P$ stops. The higher process starts its own election.
5. This repeats until the highest live process wins, and it informs everyone.

Example

Six processes P1 to P6 exist, and P6 is the coordinator. P6 crashes, and P2 notices it.

• P2 sends ELECTION to P3, P4, P5 and P6.
• P3, P4 and P5 reply with OK, and P2 stops. P6 is dead and does not reply.
• P3 sends ELECTION to P4, P5 and P6. P4 and P5 reply with OK.
• P4 sends ELECTION to P5 and P6. P5 replies with OK.
• P5 sends ELECTION to P6. There is no reply, so P5 wins.
• P5 sends COORDINATOR to all the processes.

Advantages

• It is simple to understand and to implement.
• It always selects the process with the highest ID, so exactly one coordinator is chosen.
• A recovered process with a higher ID can take over at once, and it does not wait.

A logical clock is a counter that gives each event a number to show the order of events, without using real time. Lamport's logical clock is the best known.

• Each process increases its counter before every event.
• A message carries the sender's counter value.
• On receiving a message, the process sets its counter to the larger of its own value and the message value, plus one.

It helps because the physical clocks of different computers are never exactly equal. Logical clocks give a consistent order of events (the happened-before relation), which is what many algorithms need.

Distributed commit makes sure that a transaction that is spread over many machines is either committed at all of them or aborted at all of them. The usual method is the two-phase commit.

• Phase 1 (voting): the coordinator asks every participant "can you commit?". Each one replies yes or no.
• Phase 2 (decision): if all say yes, the coordinator sends COMMIT. If any says no, it sends ABORT.

Example: a transfer of money from a bank A to a bank B. A subtracts the amount, and B adds it. Either both do it, or neither does.

Recovery: every participant writes its steps in a log before it acts. After a crash, it reads the log and completes or undoes the transaction. Checkpoints limit how much of the log is read.

Cristian's algorithm synchronises a client clock with a time server.

Steps

1. The client records the time $T_0$ and sends a request to the time server.
2. The server replies with its current time $T_s$.
3. The client records the time $T_1$ when the reply arrives.
4. The round trip time is $RTT = T_1 - T_0$.
5. The client assumes that the reply took half of the round trip, and sets its clock to:

Example

The client sends the request when its clock shows 5:08:15.100, and the reply arrives at 5:08:15.900. The server time in the reply is 5:09:25.300.

The client sets its clock to 5:09:25.700.

Notes

• Cristian's algorithm is meant for systems where the delay of the network is small compared with the accuracy that is needed, such as a local network.
• The accuracy is limited by the RTT. The error is within plus or minus $RTT/2$.
• The clock must never be set back. If the client clock is ahead, it is slowed down slowly.
• The method fails if there is only one time server, and it is down. Many servers are used to avoid this.
• The client may send the request several times, and take the reply with the smallest round trip time. This gives the smallest error.