Distributed Systems - PDF

# Openness of Distributed Systems ## What are we talking about? Be able to interact with services from other open systems, irrespective of the underlying environment. - Systems should conform to **well-defined interfaces**. - Systems should easily **interoperate**. - Systems should support **portab...

# Openness of Distributed Systems ## What are we talking about? Be able to interact with services from other open systems, irrespective of the underlying environment. - Systems should conform to **well-defined interfaces**. - Systems should easily **interoperate**. - Systems should support **portability** of applications. - Systems should be easily **extensible**. # Policies Versus Mechanisms ## Implementing Openness: Policies - What level of consistency do we require for client-cached data? - Which operations do we allow **downloaded code** to perform? - Which QoS requirements do we adjust in the face of **varying bandwidth**? - What level of secrecy do we require for communication? ## Implementing Openness: Mechanisms - Allow (**dynamic**) setting of **caching policies**. - Support **different levels of trust** for mobile code. - Provide **adjustable QoS parameters** per data stream. - Offer **different encryption algorithms**. # On Strict Separation ## Observation The stricter the separation between policy and mechanism, the more we need to make ensure proper mechanisms, potentially leading to many configuration parameters and complex management. ## Finding a Balance - Hard coding policies often simplifies management and reduces complexity at the price of less flexibility. - There is no obvious solution. # Scale in Distributed Systems ## Observation Many developers of modern distributed systems easily use the adjective "scalable" without making clear why their system actually scales. ## At Least Three Components - **Number of users and/or processes** (size scalability) - **Maximum distance between nodes** (geographical scalability) - **Number of administrative domains** (administrative scalability) ## Observation Most systems account only, to a certain extent, for size scalability. Often a solution: multiple powerful servers operating independently in parallel. Today, the challenge still lies in geographical and administrative scalability. # Size Scalability ## Root Causes for Scalability Problems With Centralized Solutions - The computational capacity, limited by the **CPUs**. - The storage capacity, including the **transfer rate between CPUs and disks**. - The network between the user and the centralized service ## Formal Analysis A centralized service can be modeled as a simple queuing system. - **Requests** -> **Queue** -> **Process** -> **Response** ## Assumptions and Notations - The queue has **infinite capacity** -> arrival rate of requests is not influenced by current queue length or what is being processed. - **Arrival rate requests**: λ - **Processing capacity service**: μ requests per second. ## Fraction of Time Having K Requests in the System $P_k = \frac{\lambda^k}{\mu^k(1-\frac{\lambda}{\mu})^k}$ ## Utilization U of a Service is the Fraction of Time That It is Busy $U = \sum_{k>0}P_k = 1 - P_0 = \frac{\lambda}{\mu} = (1 - U)\frac{U}{\mu}$ ## Average Number of Requests in the System $N = \sum_{k\geq0} k\cdot P_k = \sum_{k\geq0} k\cdot (1-U)U^k =(1-U)\sum_{k \geq 0}k\cdot U^k= (1-U)\frac{U}{(1-U)^2} = \frac{U}{1-U}$ ## Average Throughput $X = U\cdot\mu + (1-U)\cdot 0 = \frac{\lambda}{\mu}\cdot\mu = \lambda$ ## Response Time: Total Time Take to Process a Request After Submission $R = \frac{N}{X} = \frac{NS}{1 - U} => R = \frac{1}{S}\frac{1}{1-U}$ Where $S = \frac{1}{\mu}$ being the service time. ## Observations - If U is small, response-to-service time is close to 1: a request is immediately processed. - If U goes up to 1, the system comes to a grinding halt. Solution: decrease S. # Client-Server vs. P2P: Example - Client upload rate = u, F/u = 1 hour, u₃ = 10u, dmin 2 us. This image shows a graph with two lines. The first line, labelled 'P2P', begins at coordinate (0,0), and steadily rises at an increasing rate until the final coordinate (35,3.5). The second line, labelled 'Client-Server', begins at coordinate (0,0) and initially rises at a similar rate to that of the first line, but only rises to (35, 1). This line has a steep upward slope, and then levels out reaching a plateau at x = 10 and onward. # Problems with Geographical Scalability - **Cannot simply go from LAN to WAN**: many distributed systems assume synchronous client-server interactions: client sends request and waits for an answer. Latency may easily prohibit this scheme. - **WAN links are often inherently unreliable**: simply moving streaming video from LAN to WAN is bound to fail. - **Lack of multipoint communication**, so that a simple search broadcast cannot be deployed. Solution is to develop separate naming and directory services (having their own scalability problems). # Problems With Administrative Scalability ## Essence Conflicting policies concerning usage (and thus payment), management, and security. ## Examples - **Computational grids**: share expensive resources between different domains. - **Shared equipment**: how to control, manage, and use a shared radio telescope constructed as large-scale shared sensor network? ## Exception: Several Peer-to-peer Networks - File-sharing systems (based, e.g., on **BitTorrent**). - Peer-to-peer telephony (**Skype**). - Peer-assisted audio streaming (**Spotify**). **Note**: end users collaborate and not administrative entities. # Techniques for Scaling ## Hide Communication Latencies - **Make use of asynchronous communication** - Have separate handler for incoming response - **Problem**: not every application fits this model. ## Facilitate Solutions by Moving Computations to Client This image shows two different scenarios. Both scenarios have a client and a server. - The first scenario shows a box labelled "Client" containing a form with three fields: "First name", "Last name", "E-mail". The form is filled out with the details of the client, with an arrow pointing to the "Server" box. The text "Check form" is placed above this arrow. - The second scenario shows two boxes labelled "Client" and "Server", joined by two separate arrows pointing in opposite directions. The arrow pointing from "Client" to "Server" is labelled "Check form", and the arrow pointing from "Server" to "Client" is labelled "Process form". The first "Client" box contains a form similar to the first scenario, but here, the form is already filled out. The second "Client" box contains nothing but the text "MAARTEN\nVAN STEEN\[email protected]". This scenario shows a solution where computations happen on the client side, so that less work has to be done on the server side. ## Partition Data and Computations Across Multiple Machines - Move computations to clients (**Java applets**) - **Decentralized naming services** (**DNS**) - **Decentralized information systems** (**WWW**) ## Replication and Caching: Make Copies of Data Available at Different Machines - **Replicated file servers and databases** - **Mirrored Web sites** - **Web caches** (in browsers and proxies) - **File caching** (at server and client) # Scaling: The Problem With Replication ## Applying Replication is Easy, Except for One Thing - Having multiple copies (cached or replicated), leads to **inconsistencies**: modifying one copy makes that copy different from the rest. - Always keeping copies consistent and in a general way requires **global synchronization** on each modification. - **Global synchronization** precludes large-scale solutions. ## Observation If we can tolerate inconsistencies, we may reduce the need for global synchronization, but tolerating inconsistencies is **application dependent**.