25-Comp-B10 Distributed Systems · May 2017
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.
(a) Differences and similarities between distributed and centralized systems. Similarities. Both are built from the same fundamental building blocks — processes that hold state and execute instructions, communicating to accomplish some overall task — and both must ultimately satisfy the same functional requirements for their users (correctness, availability, reasonable response time); a well-designed application can often be described at the same level of abstraction (client requests a service, service returns a result) whether it runs as threads inside one process or as separate processes on separate machines. Differences. A centralized system has a single point of control: one memory space, one clock, one scheduler, so concurrency and resource access can be serialized exactly and failure is all-or-nothing (the whole system stops). A distributed system instead has multiple independent, autonomous components that communicate only by passing messages over a network with no shared memory and no shared clock, which introduces properties a centralized system never faces: partial failure (some nodes up, some down, and no immediate way to tell dead from merely slow), no single global notion of "now" (making event ordering hard), unpredictable communication latency, and the network itself as an additional failure mode. The practical consequence is that a distributed system's components must be designed assuming concurrency, partial failure and message delay are the normal case, not exceptional ones.
(b) Client-server architecture. The client-server architecture is the most widely used distributed-system architecture: a server is a program that runs continuously (or on demand), listens on a well-known network address/port, and provides a defined service by responding to requests; a client is a program that initiates communication by sending a request to a server and consuming the reply, typically on behalf of an interactive user. The relationship is asymmetric — the server is passive (waits to be asked) and is typically shared by many concurrent clients, while each client instance is usually private to one user or task and initiates the interaction — and the two communicate over a network using a request-reply protocol built on transport-layer sockets (TCP or UDP). The Web (illustrated above) is the canonical example: a browser (client) sends an HTTP request naming a resource to a Web server, which processes it and returns the requested content; the same skeleton generalizes to email (an SMTP/IMAP client talking to a mail server) and ftp (a control connection to negotiate commands plus a separate data connection for the file transfer). In every case the server exposes a stable, addressable service and the client is the one that must know where to find it and initiate contact.
(c) Resource sharing in distributed systems. Resource sharing is the ability of hardware resources (printers, disks, specialized processors), data (files, databases) and services (a search index, a payment gateway) owned by one component of a distributed system to be used by processes running on other components, coordinated through a manager that controls consistent, concurrent access. Advantage 1 — economy of scale and utilization. Expensive or specialized resources (a high-speed printer, a large database, a compute cluster) can be centralized once and shared across an entire organization rather than duplicated at every workstation, and idle capacity on one machine can be used by processes running elsewhere instead of sitting unused. Advantage 2 — collaboration and data consistency. Multiple users/processes can work from one authoritative, shared copy of data (a shared file, a shared calendar, a shared database) instead of each keeping a separate, potentially diverging local copy, which is what makes collaborative applications (shared documents, groupware) possible at all. Disadvantage/challenge 1 — concurrency control. When many clients can access the same shared resource simultaneously, the resource manager must serialize or otherwise coordinate conflicting concurrent accesses (locking, transactions, optimistic concurrency) to avoid lost updates or inconsistent reads — a problem that simply does not arise when a resource is private to one process. Disadvantage/challenge 2 — availability and security exposure. A shared resource becomes a single point of contention and failure for every client that depends on it (an outage now affects many users at once instead of one), and because it must be reachable over the network by many different, sometimes untrusted, clients, it is also a much larger attack surface than a resource that never leaves one machine's protected memory.
(d) Factors contributing to message delay, and how each is bounded. The total time to deliver a message between two processes decomposes into several distinct components, each governed by a different physical or design factor. 1. Propagation delay — the time for a signal to physically traverse the medium, set by distance and the signal's propagation speed in that medium (roughly the speed of light for fibre/copper). It is bounded mainly by topology: placing communicating processes and replicas geographically closer (edge servers, regional data centres, CDNs) shortens the physical distance a signal must cross. 2. Transmission delay — the time to push all of a message's bits onto the link, equal to message size divided by link bandwidth. It is bounded by provisioning enough bandwidth for the expected message sizes and traffic volume, and by keeping messages small (compression, sending only deltas) when bandwidth is scarce. 3. Processing delay — the time each intermediate node (router, switch) and the endpoints themselves spend examining a packet's header, deciding how to route it, and running protocol-stack code (checksums, marshalling/unmarshalling). It is bounded by using efficient routing hardware/algorithms and lightweight, low-overhead marshalling formats. 4. Queuing delay — the time a packet waits in a router's or a receiving process's buffer behind other traffic before being serviced, which grows sharply, and unpredictably, as a link or server approaches saturation. It is bounded by admission control and traffic engineering — keeping utilisation below saturation, prioritising latency-sensitive traffic (QoS), and provisioning enough capacity that queues stay short under expected load. 5. Access/medium-contention delay — on a shared medium (e.g. a shared Ethernet segment or a wireless channel), the time a sender must wait for its turn to transmit at all, governed by the medium-access-control protocol. It is bounded by using switched (collision-free) rather than shared media, or by scheduling access more efficiently (TDMA-style slotting, priority contention windows). None of these five factors can be reduced to zero, which is why distributed-system protocols are designed to tolerate variable delay (timeouts, retransmission, buffering) rather than assume it can be eliminated.
