Distributed Systems Flashcards
(96 cards)
1
Q
What are the advantages for organizing concurrent computation as threads instead of processes?
A
Low overhead on creation
Low overhead for context switching
Allows for easier sharing of resources
2
Q
What are the advantages for organizing concurrent computation as processes instead of threads?
A
Allows for scalability and fault-tolerance (processes are more independent)
3
Q
What is involved in converting a single, multi-threaded application into a collection of single-threaded processes. What could change about the application’s implementation and why?
A
- Shared resources are not shared when converted to processes, so this will need to be managed in some way.
- Communication will change to pipes/sockets. Computation that runs concurrently may need to be changed based on the way it is implemented with the threads.
- Overhead will need to be considered on startup of multiple processes and how many can run at once.
- Method of concurrent computation may need to be changed (barrier, signals, etc. instead of waiting on threads to finish)
4
Q
Describe some low-level message framing strategies.
A
Fixed length
- you know the exact size of each message
- can easily determine if you have failed to receive the entire message
- could increase network traffic as more messages need to be sent from component to component
Variable length
- allows for more message flexibility
- need a way to determine the end of the message
- still may need to send multiple messages if a message is larger than the network allows or component allows
5
Q
What are quorum-based decisions?
A
A minimum number of votes before a distributed transaction is carried out. Typically this is more than half of the nodes on the system.
6
Q
What is a race condition?
A
The system’s behavior is dependent upon the timing of the logic. This can lead to inconsistencies (different results depending upon execution time) in results that the system provides.
7
Q
What is the difference between two-phase and strict two-phase locking?
A
Both acquire a lock before critical code is executed and release a lock when it has completed critical code. Strict two-phase disallows the release of a lock until a “moderator” sends a signal for release.
8
Q
How would switching from proxy to broker simplify an application?
A
It would not simplify the application and it could make it more complicated. A broker is more generic than a proxy and while it could lead to more flexibility fro messages within the system, it is typically more difficult to implement this kind of flexibility. You could potentially gain functionality if moving from a single proxy and nothing else to a single broker and nothing else.
9
Q
How would switching from broker to proxy simplify an application?
A
Less flexibility in messaging would make the component’s interfaces easier to implement. The proxy is all about access control so that is all it is required to do. You could potentially lose functionality if moving from a single broker with nothing else to a single proxy and nothing else.
10
Q
What is the CAP theorem?
A
You cannot have all three in a distributed system
Consistency: Every read gets the most recent write
Availability: Every request receives a non-error response
Partition tolerance: The system continues to operate despite an arbitrary number of drops
11
Q
What are some issues with network-based communication?
A
Performance - latency and data transfer rate
Scalability - what hardware/software is needed to scale
Security - typical network-based security concerns
12
Q
What is RPC?
A
Remote Procedure Call
13
Q
What are some issues with RPC?
A
- Call by value or call by reference?
By value - a copy is passed
By reference - the actual value is passed - Byte ordering for parameters (big or little endian)
14
Q
What is the difference in big- and little-endian?
A
Big endian - most significant bytes are first
Little endian - least significant bytes are first
15
Q
What byte-ordering is important in distributed systems?
A
Network order - always big endian
Host byte order - depends on the machine
16
Q
Access point definition
A
a means of access to an entity
17
Q
Address definition
A
a location for an access point
18
Q
Name definition
A
a string that references an entity
19
Q
What is flat naming?
A
Names are unstructured bit strings that have no obvious connection to their referents
Example
MAC address
20
Q
What is structured naming?
A
Names composed of multiple, supporting names
Example
IP addresses
21
Q
What is attribute-based naming?
A
Names derived from the attributes of their referents (directory service). Given a service category, find a node that provides that service.
Example
LDAP
22
Q
How to provide fault tolerance in a distributed system?
A
Exploit redundancy
Hot swap (backup that is up to date with the current component) ready to go on failure Distributed information (one or more components can fail but the system can be reconstructed from the remaining components)
23
Q
What is page-based DSM?
A
Distributed shared memory based on paging.
24
Q
Why used DSM over RPC?
A
- Entire distributed system is logically one muti-threaded application
- No need to worry about passing parameters from machine to machine
25
Why use RPC over DSM?
- Easier to deal with failure
- Method calls should be the same across all components of the system
- No need to worry about typical shared memory constructs
26
Name the different architectural styles of distributed computing according to Phil.
Unstructured - styles with no theoretical limits on how entities are coupled
Structured - styles that organize entities in ways that limit what entities a given entity can interact with directly
27
What are the pros and cons for unstructured styles?
Advantages
- simplicity of system's internal organization
- ease of access among system's entities
Disadvantages
- increased difficulty of monitoring and maintaining system operation, due to range of possible interactions among the entities
- worst case it can be a fully connected (mesh) network that requires O(n^2) connections for interactions
28
What is a distributed hash table?
- schemes that distribute content across objects using a function that's computed from items' keys
29
Give 2 ways to represent an unstructured style.
object-based - unordered collection of components
| resource-based - unordered collection of resources
30
How are object-based styles implemented?
- definitive version of object, including its state, positioned at a single, base node in a distributed network
- to use an object, other nodes bind to it, then access it
- the bind creates proxy representation of the remote object at local host
31
What is a proxy?
a software construct that controls access to other objects; it redirects access to the remote object and relays remote object's responses to local hosts
32
Assess object-based style.
Advantages
- can improve application transparency by blurring distinction between remote and local objects
- natural model for session-based interaction with remote objects
- natural model for encapsulating data
Disadvantages
- can't fully mask impact of network on communications (network failure, remote host failure, impracticality of duplicating large amounts of local host state at remote object site)
- excessive use of objects can degrade host performance, creating computational bottlenecks
33
Assess session-based interaction.
Advantages
- simplifies an application's coding
- reduces flow of traffic across the network
Disadvantages
- state information of the remote object must be maintained
- lends itself to high duplication of data
- increases complexity of the messages (every message must be self-contained so this may lead to reauthentication for every message in session)
34
How are resource-based styles implemented?
- resources are identified via a standard naming scheme
- services offer a uniform, message-based interface
- messages are self-describing
- resources maintain no state on callers
35
Give an example of resource-based implementation.
REpresentational State Transfer (REST)
36
Describe REST.
- resources named using Uniform Resource Indicators (URIs)
- offers a CRUD-style, PUT-GET-POST-DELETE protocol for managing state
- communication protocol (HTTPS) is still stateless
37
Assess resource-based interaction.
Advantages
- reduces performance impact on remote object host by eliminating need to for host to maintain state
- simplifies service implementation by removing need for remote object host to recover from host and network failure
Disadvantages
- potentially complicates client-side implementation
38
What are the different types of structured styles?
- Horizontal
- Commons-based
- Layered
- Hierarchical
- Other miscellaneous
39
Assess structured-based styles.
Advantages
- facilitates maintaining system operation due to limiting of direct object interaction
- accommodates networks where some indirect interactions are unsupported
Disadvantages
- restrictions complicate system fabric by introducing need for routing of communications between indirectly connected entities
- restrictions increase probability of network partitioning
40
Describe horizontal styles.
- roughly, a linked-list representation of objects
- can be strict (left and right neighbor) or loose (left and right neighbor with O(1) shortcut to other objects in the architecture)
- can be singly- or doubly-linked (one-way or two-way request flow)
41
Assess horizontal styles.
Advantages
- conceptually and operationally simple
Disadvantages
- specialized applicability
42
Give 2 examples of horizontal styles.
Linear: strict horizontal style where start and end node are not connected
- something like a message parser (decrypt, authenticate, remove duplication, etc.)
Ring: loose horizontal style where start and end node are connected with potential chords throughout the structure
- distributed hash table
43
Give 2 ways to implement distributed hash tables.
Regular ring
- you have nodes used for lookup
- each lookup node has keys associated with it
- if node is in the current node's lookup table, great, jump to it
- if not, go to next lookup node
Chordal
- each chord contains a finger table that references other nodes on the network
- to look for node n, visit the first node with a finger table
- if node n is in the finger table, great, jump there
- if not, visit the largest node in the finger table that does not exceed the desired node
- repeat until node is found
- if nodes in the finger table are all larger, hop to next node (linear search) until node is found or another valid finger table is found
44
Describe commons-based style.
- any style that is referentially decoupled
- components interact via a central information hold
- the central information center contains information about the computational environment
45
Describe referential coupling.
- referentially coupled requires entities to explicitly name each other when communicating
- referentially decoupled entities do not name each other when communicating
46
Describe 2 different ways for centralized commons to be organized.
Entity-oriented (temporally decoupled)
- the commons functions as a shared store
- items in the commons can be accessed indefinitely until removed
Event-oriented (temporally coupled)
- items in the commons have a limited useful lifespan
- each item can only be accessed by processes that are active when that item was added to the commons
47
Describe layered styles.
- components are organized into groups and stacked such that modules in a layer depend on modules beneath them
- full/strict/closed (layer n is limited to reference n-1)
- partial/open (layer n can reference all layers below)
48
Assess layered styles.
Advantages
- aids understanding when clear decompositions of components into layers is achievable
- aids maintainability by isolating concerns by layer
- aids portability and adaptability by allowing for substitutions by layer
Disadvantages
- functionality can be difficulty to layer
- layering potentially decreases performance
49
Describe hierarchical styles.
- generalization of layered style where system's components interact along lines of communication that are structured as trees
Advantages
- applicable to networks with limited element-to-element connectivity
- strikes a balance between component proximity and number of connectors
- intuitive
- algorithmic techniques for tree manipulation are well-known
50
Define architectural style.
strategy for organizing elements and their interactions
51
Give an architectural example of an unstructured, object-based style.
Unstructured Peer
52
Describe an unstructured peer system.
- system organized as a graph of random connections
| - requests and data flow through system using various ad-hoc techniques
53
Discuss 4 peer system routing strategies.
Flooding - each node distributes all messages to all neighboring nodes
Random walk - messages follow random pathways through the network
Anti-entropy - push-pull on random nodes
Gossiping - nodes distribute messages to their neighbors with a given probability, either fixed or based on history (informed gossip)
54
Assess unstructured peer.
Advantages
- readily distributes over a network
- easy to scale
- easy to reuse
Disadvantages
- difficult to analyze and debug due to relative lack of structure
- difficult to provide interoperability in networks of heterogeneous components
55
Give an architectural example of an unstructured, resource-based style.
Microservice architecture
56
Describe a microservice architecture.
- graph of small services defined by their APIs
| - each microservice has arbitrary connections to the others
57
Assess microservice architectures.
Advantages
- low coupling, autonomous, flexible
- maps well to DevOps
- independently scalable
- easier deployment per service
- system should be more available
Disadvantages
- end-to-end testability is more difficult
- logging and overall performance monitoring is harder
- can get very complex if there are many components
- performance suffers, due to latencies from repeated message passing
58
Give an example of a horizontal architectural style.
Pipe-and-filter
59
Describe a pipe-and-filter architecture.
- upstream components accept data, process it, and pass it downstream
- architecture must coordinate data flow (asynchronous and synchronous flows)
Example - compilers
60
Assess pipe-and-filter architectures.
Advantages
- simple to implement
- lends itself toward reusable components
- easy to maintain
- provides a natural basis for concurrency
Disadvantages
- error handling (no global state, restart is often difficult)
- data flow must be uniform along pipes for best performance
- forces batch mode processing
61
Give 2 examples of data-oriented architectures.
Repository and tuple space
62
Describe a repository architecture.
- supports communication by multiple processes through a shared, persistent store
Examples - files, registry keys, databases
63
Describe a tuple space architecture.
- specialized, distributed repository architecture when processes store, read, and retrieve tuples
64
Give 3 examples of event-oriented architectures.
Blackboard, publish-subscribe, service-oriented
65
Discuss blackboard architecture.
- like repository, but with active central store (changes to blackboard trigger events in processes)
- can either have central (events trigger in blackboard) or distributed (events trigger in processes) control
66
Discuss publish-subscribe architecture.
- like a hybrid between blackboard and repository patterns
- publishers store data to central store (looks like a write-only repository to publishers)
- subscribers register for data from server which pushes messages of interest on receipt (looks like a read-only repository to subscribers)
67
What are the advantages of publish-subscribe architectures?
- decouples publishers from subscribers (publishes can publish independently of subscribers, and subscribers can obtain content asynchronously)
- can support anonymity of both publishers and subscribers
68
Describe a service-oriented architecture.
- created to support integration of heterogeneous systems
| - allows multiple peer components to interact via a "software backplane"
69
Give 4 examples of layered architectures.
Client-server, tiered computing, broker, and proxy
70
Describe a broker.
- provided by some middleware
- allows for dynamic binding between client and service provider at beginning of interaction
Interaction sequence
- before interaction, the server registers with the broker
- a client requests a service by type
- broker responds with the address of a server that can provide the requested service
- client and server communicate directly after that
71
Describe a proxy.
- all communication occurs via an intermediate process
| - shields server(s) from client
72
Compare client-server, broker, and proxy
Client-server vs. broker, proxy
- simpler
- faster: no initial or intermediate communication
Broker
- vs. client-server: more flexible and scalable (broker can route all requests to any server at the start of a session)
- vs. proxy: faster (less overhead for multi-message session)
Proxy
- vs. client-server: more flexible and scalable (allows proxy to route any requests to any server at any point during a session)
- vs. broker: more secure (hides server(s) from client throughout session)
73
Discuss service provisioning.
3 types
- Infrastructure as a Service (IaaS): network-accessible resources that function as machines
- Platform as a Service (PaaS): network-accessible resources that function as operating systems
- Software as a Service (SaaS): network-accessible resources that function as individual services
Management
- On-premises: you manage everything
- IaaS: you manage everything up to the OS
- PaaS: you manage the applications and data
- SaaS: you manage nothing (only use the service)
Standardization
- IaaS: instruction sets (achieved through virtualization)
- PaaS: application environments; Linux, Windows, etc.
- SaaS: applications
74
What is the difference between virtual machines and virtualization?
- virtual machines do not mirror read hardware
| - virtualization mirrors real hardware
75
What is the difference between asynchronous and synchronous network communication?
- with synchronous communication, the client blocks further processing until the request is handled (wastes cycles but the handling of the request -- success/failure -- is easily known)
- with asynchronous communication, the client spins a thread/process to make the request while continuing other processing (no wasted cycles but the handling of the request is not easily known)
76
What is the TCP/IP model?
```
Application
Transport
Internet Protocol
Network Access
Physical
```
77
What is marshalling/unmarshalling?
- the serialization/deserialization of objects/data
78
Describe middleware in a distributed system.
- provides extra support for distributing functionality across a network, typically through providing adapters for relaying messages
Example - MPI
79
What is the main issue with delivering multimedia in a distributed system?
- how does the system ensure that the flow of data is timely enough to meet user expectations for presentation quality in real-time
80
What are some basic options for reducing communications overhead in a distributed system?
- reduce the overall number of messages
- reduce time to send via caching
- eliminate needless content
81
What is the difference between authentication and authorization?
- authentication provides access control to the overall system via passwords, usernames, digital fingerprints, etc.
- authorization provides access control to content/resources within the system via user groups
82
Describe hierarchical routing.
- overlay routing network arranged in the form of a tree
- tree is balanced (as much as possible)
- to find a node on the network, start at leaves and work up
83
Describe asymmetric (public-key) cryptography.
- uses two keys
- public key can be distributed to anyone
- private key only known by the holder
- to encrypt a message, the sender uses the receiver's public key
- to decrypt a message, the receiver uses their private key
84
Describe coordination in a distributed system.
- ensure that relationships between components hold true at specified points in time
- two different strategies (centralized and distributed)
85
What are the two basic approaches to time in a distributed system?
Absolute (physical) time - using time to coordinate action
Relative (logical) time - using exchanges of messages among cooperating processes to sequence actions
86
Discuss some difficulties with physical time.
- difficult to measure
- transmissions of time are subject to jitter
- clocks drift, creating skew
87
Define jitter.
- variability in message latency
88
Define latency.
- time between message send and receipt
89
Define clock drift.
- tendency of a clock to run at a different rate from a reference clock
90
Define clock skew.
- difference between a reference clock and other clocks
91
How do we adjust for jitter and skew in time?
- Cristian's algorithm - a.k.a. Network Time Protocol (NTP)
- Berkeley algorithm
- Reference Broadcast Synchronization (RBS)
- Google's TrueTime
92
Describe Cristian's algorithm.
- host requests UTC from time server, remembers as T1
- time server sends T2 (receipt of request) and T3 (when response was sent)
- T4 is when the response was received by the host
- host adjusts T3 by ((T2 - T1) + (T4 - T3))/2
93
What is mutual exclusion?
- limiting number of processes that can access a pool of resources at any one time
94
What are two basic strategies for assuring mutual exclusion?
- token-based: process seeking access acquires a token and keeps access until surrendering token
- permission-based: process seeking access obtains permission before acting
95
What are two basic strategies for implementing each mutual exclusion assurance measure?
- centralized: one coordinating process manages access to resource
- decentralized: competing processes coordinate access together
96
What are the two basic levels of consistency?
- strict consistency: each read retrieves the most recent write to the resource
- eventual consistency: reads are not guaranteed to contain the most recent writes to the resource but they will eventually have the most recent updates over time
