25-Comp-B10 Distributed Systems · May 2015
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) Alternatives to a central index for file-sharing. A single central index (as used by early services such as Napster) is a scalability bottleneck and a single point of failure: every lookup and every peer's periodic "here is what I hold" update must pass through it, so its capacity caps the whole system's size and its outage stops all lookups everywhere. Three broad classes of alternative have been used since: (1) Flooded/broadcast query, fully decentralized. Every peer holds only its own resources; a lookup request is forwarded to a peer's immediate neighbours, who forward it to theirs, up to a hop-count limit (Gnutella's original design). There is no index at all to build or maintain, and no single point of failure, but the query traffic itself grows with the network's size and depth, so this does not scale well either past a modest number of peers. (2) Hierarchical / super-peer indexing. A subset of more capable, well-connected peers ("super-peers") each maintain an index of the resources held by a cluster of ordinary peers beneath them, and super-peers query each other (or flood among themselves) to answer a lookup that its own cluster cannot satisfy. This restores much of a central index's lookup efficiency while removing the single point of failure and distributing the indexing load across many super-peers instead of one server (used by later Gnutella/Kazaa-style networks). (3) Structured, fully decentralized indexing via a distributed hash table (DHT). Every peer and every resource key is mapped, by a common hash function, onto the same identifier space (e.g. Chord's ring, Pastry's or Tapestry's prefix-routed mesh, CAN's coordinate space); a peer responsible for a given key range answers lookups for keys in that range, and routing to the responsible peer takes only $O(\log N)$ hops for $N$ peers, with no peer ever holding a full index. This gives guaranteed, bounded-hop lookup with no central bottleneck and no query flooding, at the cost of extra bookkeeping every peer must do to maintain its small local routing table as peers join and leave.
(b) Client and server programs. In the client-server model, 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 typically shared by many concurrent clients, while each client instance is usually private to one user or one task and initiates the interaction. The two communicate over a network using a request-reply protocol built on top of transport-layer sockets (TCP or UDP): the client marshals its request into a message, sends it to the server's address, and blocks (or polls asynchronously) until the reply message arrives.
The same skeleton generalizes to email and ftp: an email client speaks SMTP to a mail-submission server and IMAP/POP3 to a mailbox server to fetch messages; an ftp client opens a control connection to negotiate commands and a separate data connection for the actual 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) Distributed vs. centralized systems — three advantages, three disadvantages. Advantage 1 — resource sharing and incremental scalability. A distributed system lets many independent machines' processing power, storage and peripherals be pooled and shared across an organization, and capacity can be grown incrementally by adding more machines rather than being permanently bounded by whatever ceiling a single centralized machine happens to have. Advantage 2 — fault tolerance and availability. Because functionality and data can be replicated across independent nodes, the failure of any one machine need not halt the whole system — other nodes continue serving, whereas a centralized system has a single point of failure: one crash stops everything. Advantage 3 — openness and heterogeneity. A distributed system built on open, published interfaces and protocols lets components from different vendors and different hardware/OS platforms interoperate and be upgraded or replaced independently, whereas a centralized system's internal design is free to be a closed, monolithic whole with no such interoperability pressure — useful, but it also means the centralized system cannot easily absorb best-of-breed components from outside.
Disadvantage 1 — added complexity. A centralized system has one clock, one memory, and no partial failure or concurrent access from a network to reason about; a distributed system must additionally handle concurrency, partial failure (some nodes up, some down), the absence of a single global clock, and unpredictable message delay — all of which make correctness far harder to reason about and to test than a single-machine program. Disadvantage 2 — security exposure. Every message that crosses the network between nodes is a potential interception or tampering point, so a distributed system must actively defend an inherently open, shared network path between its components, whereas a centralized system's data mostly stays inside one machine's protected memory and never has to cross an untrusted wire at all. Disadvantage 3 — dependence on unpredictable network behaviour. A distributed system's overall responsiveness and even its availability are now hostage to a network the application does not control — variable latency, congestion, and outright partitions can each degrade or stop the service even though every individual machine is healthy, whereas a centralized system's components talk over a fast, private internal bus whose behaviour is essentially deterministic by comparison.
