Fichas
DS
Fichas del conjunto (61)
- 1Can multiple clients read and write to the same shared memory at the same time?False, only one can write but multiple clients can read in parallel
- 2Is Shared Memory a fast process?It is fast if done locally, and because of simultaneous read can be very efficient in terms of algorithmics
- 3What is Synchronisation / Mutal exclusionIt is a technic used to prevent memory inconsistencies (data races). For example in a linked list when two clients trying to remove two different links only one can be removed at the same time since it a critical.
- 4What is Message Passing?When processes exchange information by sending and receiving messages, either locally or remotely. Messages can be sent to one receiving process, several, or even broadcast.
- 5Is Message passing delay incurring or not?It is typically delay incurring.
- 6Can, so-called, dead-locks occur in Message Passing?Yes even though synchronization is implicit
- 7What type of system would you use if you would only want to receive certain(classes of) messages?Publish/Subscribe systems
- 8What does CORBA stand for and what is it?Common Object Request Broker Architecture. It is a standard defined designed to facilitate the communication of systems that are deployed on diverse platforms.
- 9What is RPC?In distributed computing, a remote procedure call (RPC) is when a computer program causes a procedure (subroutine) to execute in a different address space (commonly on another computer on a shared network), which is coded as if it were a normal (local) procedure call, without the programmer explicitly coding the details for the remote interaction.
- 10What is RMI?RMI (Remote Method Invocation) is a way that a programmer, using the Java programming language and development environment, can write object-oriented programming in which objects on different computers can interact in a distributed network. RMI is the Java version of what is generally known as a remote procedure call (RPC), but with the ability to pass one or more objects along with the request.
- 11Explain the scheme for Synchronous interactionThe scheme then:
Make a call/request
Wait for the execution
Receive the result
Possibly with a timeout - 12Explain the scheme of Asynchronous InteractionThe execution time of an Asynchronous request is either not known or known to be possibly “long”.
The scheme is:
Make a call/request
[Do own execution…]*
Receive and process the result - 13If you compare TCP and UDP to synchronous and asynchronous. Which one which?TCP is synchronous
UDP is asynchronous - 14What does Thread.currentThread().join(); do?Thread.currentThread().join() blocks the current thread forever unless the program is killed, e.g. with CTRL+C on Windows.
Without that line, the main method would exit right after the server is started if no loops were implemented
An alternative would have been to use Thread.sleep(Long.MAX_VALUE);
Thread.currentThread().join(); is a statement that takes forever to complete. - 15Why is it bad to have this approach when dealing with synchronization: counter = counter + 1?It is two distinct variable accesses, the variable might have been updated in between. Even though each of them is atomic. Instead, implement a method with synchronized on it. See image for example.
- 16What class does the functions: Wait and notify(All) belong to?Object. Bonus:
A basic requirement is that they have to be called from within a
synchronized context for the given object.
- 17Explain these words: Destination, Socket, Ports, AddressDestination:
Internet address and local port
Socket:
abstraction of the connection, UDP or TCP
Ports:
large range (16 bits datatype), one process can use multiple ports, but
one port cannot be shared between processes (with an exception for multicast)
Address:
a named host or direct IP address, 4 bytes A.B.C.D (for IPv4) - 18What risk does Omission failures refer to within UDP?packets are not guaranteed to be delivered, nor are
acknowledged - 19Define Marshalling (unmarshalling is the opposite)“The process of taking a collection of data items and assembling them into a form
suitable for transmission in a message. Marshalling consists of the translation of
structured data items and primitive values into an external data representation.” - 20What does "External data representation" mean?Something that “everyone” understands
It allows data to be transferred between different kinds of computer systems. - 21What is an Tagging interface?An interface for the purpose of its own existence. That is, it does not declare any methods!
- 22What is XML and what is its purpose?A W3C standard (with siblings) for encoding documents and structured data in a human-readable(hence also ASCII transportable) and machine-readable form
- 23What does JAXB stand for and what is it?Java Architecture for XML Binding and it's a framework that supports marshalling of Java objects into XML and unmarshalling XML data to Java objects
- 24Explain the Map-reduce process1.
Break the input data into chunks, mark each chunk with somekey1. Each node gets one key with the associated data.
2.
The mapping part: Each node processes (map function) one chunk and produces an intermediate result, a list of key2-value pairs.
3.
The reducing part: Intermediate results from the mapping nodes are grouped by key2 and distributed to reduce nodes which consolidate the output (reduce function) for each key. Modularisation Only the map and reduce functions are user provided, the rest of the work is done by the framework / library. - 25What does Atomicity mean?Atomicity means that either you update everything or nothing.
- 26Give a few examples of failures that can occur with Concurrent AccessFor example, if you have two bank cards for the same account and you use them in two different shops at the same time, you might have insufficient resources.
People ordering from your shop online at the same time but only one of the item is available - 27What are the ACID Properties on transactions?Atomicity – all updates must be performed or none, also in case (and
particularly) of failures
Consistency – a transaction takes the system from one consistent state to
another consistent state
Isolation – No interference from other transactions, the intermediate effects of
a transaction should not be visible to other transactions
Durability – When successful, all effects of the transaction should be saved in
permanent storage and recoverable even after a subsequent system crash - 28How is Serial / Sequential Equivalence ensured?An interleaving of two transactions is said to be serially equivalent if its results are the same as if the transactions have been executed in isolation in some order.
To get serial equivalence we need to control the possible interleavings. To do that we employ different concurrency controls to ensure that possibly conflicting operation
(reads or writes) happen in the right order. One of such controls is locking. - 29What is a Cascading Abort?When one transaction aborts, then any other transaction modifying the same data has to abort too. This, in turn, can cause aborts of the more related transaction resulting in a cascading abort.
- 30Explain Strict two-phase lockingTo allow strict execution regime, any new transaction can only read/write data once the other transactions in progress have committed. This is called strict two-phase
locking. It prevents dirty reads and premature writes. - 31Give me two real life examples of locking on concurrencyYour bank account would be locked. This would be an equivalent of going there in person and taking the nummerlap for a
very long queue!
Ordering tickets to shows online that are very popular. You can first go in and order once the timer for the first people in cue are finished. - 32What are Protocol Buffers?Protocol buffers are nothing more than Google specific serializable messages
(simplified and high-performance) for internal communication within the
infrastructure, including remote innovation, which is language independent and open source. - 33What is Sawzall?Sawzall is a higher-level language for Google’s Map-Reduce.
- 34What is GFS, Chubby and Bigtable and what do they have in common?GFS
Google File System, a Distributed file system for unstructured data (files), optimized for Google style of
files (=very large files).
Chubby
Supports distributed locking and small quantities of data.
Bigtable
Storage of structured data, so essentially a database infrastructure, Google style –
simplified for performance, does not support full relational operators. - 35What is POSIX?The Portable Operating System Interface (POSIX) is a family of standards specified
by the IEEE Computer Society for maintaining compatibility between operating systems. POSIX defines the application programming interface (API), along with command line shells and utility interfaces, for software compatibility with variants of Unix and other operating systems. - 36Why is time so important in DS?Imagine a legal money transaction between a merchant of some sort and a bank. Each operates on a different computer. The merchant keeps a transaction bill date according to the merchant’s clock, the bank keeps the payment record dated according to the bank’s clock. There would be certain legal requirements as to how long after the transaction the money should be or can be booked in the bank. Or just take now an everyday scenario when you buy stuff over the internet. The problem If the clocks/dates are not synchronised on both sides this can create a legal issue.
- 37Name at least 3 challenges concerning distributed systemsSecurity
Scalability
A distributed system is scalable if adding users/nodes does not cause substantial overheads in terms of maintenance or costs and doeas not create performace bottlenecks.
Example. There would be a problem if the CPU in a server can service 1000 clients concurrently but the network connection can only handle 10…
Failures
Nodes and parts of the distributed system till fail. Measures have to be taken to detect them, mitigate them, or prevent them in the first place. Some sort of redundance is typically needed to help with this.
Concurrency
Inevitable consequence of having multiple computing nodes. Synchonisation between the nodes has to be taken care of, as well as communication/data exchange. Resource access needs to be safe in the concurrent context.
Transparancy
The user would like to be totally indifferent about the fact that there are multiple nodes of the system that is being accessed, or their geographical locations.
Quality of service
This is about providiing guarantees as to operation paramters of your distributes system in terms of performance (speed - 38What is a distributed system?• A computing platform where resources are distributed and shared at the same time.
• Nodes are independentes thus concerrency /parallelism is a natural pehnomenon, with all its luggage.
• The same independence gives partial and independent failures
• No global clock
• Typically has associated programming model that helps to understans it and tame it, most importantly abstract from the hardware.
nowadays, inevitebly synonymous with Internet or web application. - 39Explain what a server isA dedicated (computational) rescource
Publicly known identity
Provides a set of defined services along with a suitable interface
Operating through request-response communication model
Can be actual or virtual - a cluster of actual computers - 40Explain what a client isA resource user
(possibly) secret identity
Needs to know services and the inerface or de able to discover them
Request-response communication model
Typically a single computer - 41What is the difference between a server and a client?The distinction between the client and the server is mostly conceptual and on the software level. In face, on a single computer you'd find applications that can be classified as clients and as servers.
- 42Explain SOAService oriented architecture
All this gives rise to the term Service and providing computing-related resource as a Service -aaS. Lame, but pragmatic view on this is that you buy the resource (software, platform) withut owning it, a kind of lease. The responsibility to maintain the corresponding infrastructure lays on the provider. What is also typical is that maintenance is continuous. - 43Explain SaaSSoftware as a Service
Typically refers to browser-initiated application software provided to multiple customers. Typical applications are business or collaborative applicationd. Google apps is one good example. - 44PaaSPlatform as a Service
When the user is allowed to deploy own applications or services, for example web servers. A set of lower level services is provided, like databases or run-time environment (Java) with a predifines API ans access levels. Amazon web seevices falls unto this category (maybe?). Office365. - 45Which algorithm achieves external synchronization?Christians algorithm
- 46Which algorithm achieves internal synchronization?Berkeley algorithm
- 47Explain clock skew and clock drift.Clock skew
Relative difference in clock values of two processes (for example, the relative difference in time between two vehicles on a road)
Clock Drift
Relative difference in clock frequencies (rates) of two processes. (This would be the difference in speed on those two vehicles). - 48What is RTT?RTT = round - trip - time
The time it takes from a message have been sent until it recieves a reply. - 49Explain Christians algorithmIt is used to achieves external synchronization.
The time P = t + (RTT-min2-min1)/2
The more accurate value you know of min2 and min1 the more accurate the estimated time till be.
Max error is (RTT-min2-min1)/2 - 50What is NTP?Network time protocol.
It is a protocol to synchronize time within a network with varying response time. - 51Explain Lamport timestampsIt is a simple algorithm used to determine the order of events in a distributed computer system.
1. A process increments its counter before each event in that process;
2. When a process sends a message, it includes its counter value with the message;
3. On receiving a message, the counter of the recipient is updated, if necessary, to the greater of its current counter and the timestamp in the received message. The counter is then incremented by 1 before the message is considered received - 52What IPC?Inter- process communication
It is how two processes within a system communicates. - 53What is a logical clock?A logical clock is a mechanism for capturing chronological and causal relationships in a distributed system. Distributed systems may have no physically synchronous global clock, so a logical clock allows global ordering on events from different processes in such systems.
Examples of logical clocks are:
Lamport timestamps and Vector clocks - 54Explain the berkeley algorithm1. A master is chosen via an election process such as Chang and Roberts algorithm.
2. The master polls the slaves who reply with their time in a similar way to Cristian's algorithm.
3. The master observes the round-trip time (RTT) of the messages and estimates the time of each slave and its own.
4. The master then averages the clock times, ignoring any values it receives far outside the values of the others.
5. Instead of sending the updated current time back to the other process, the master then sends out the amount (positive or negative) that each slave must adjust its clock. This avoids further uncertainty due to RTT at the slave processes - 55Name at least three reason for transaction failures* Insufficient resources to complete the request
* Software and hardware failures
* Communication failures
* Forceful interruptions, e.g., taking out the bank card from a payment terminal - 56Describe the typical API for transaction operationsopen or start a transaction, typically gives a transaction identifier that should be
used in the subsequent operations (but can be also implicit).
commit transaction – decide that a transaction can be completed successfully
and the changes should take effect
abort transaction – revert the system to the state before the transaction has
started - 57Concerning transactions... There are two issues that will cause inconsistencies. Which?Lost update
A data update by transaction X, which nevertheless is ineffective when all the
transactions commit.
Inconsistent retrieval
A transaction gets an outdated value or a not yet up-to-date value to perform its
own operation. - 58What is REST?Representational State Transfer. It is an
IT-architechture concept that describes how services for machine2machine communication may be provided via webbtechnology.
Varje resurs är unikt adresserbar enligt en gemensam standard (URI).
Alla resurser har ett gemensamt gränssnitt för att överföra kommandon mellan klient och server.
Till skillnad från tjänster implementerade på WS-stacken exponeras data istället för metoder. - 59What is dirty read?Lowest level of isolation. It can read before a transaction has been committed. This may cause faulty data.
- 60What is the difference between serialization, repeatable read, unrepeatable read?Serialization and repeatable read does not read a new value between transactions (?). The value must (will) always be the same. Unrepeatable read however will read the new value.
- 61what is Coordinated universal time and how can you use it within DS?Coordinated universal time (UTC in french) is an external source with highly accurate time. It can be used to sync your systems.
Información
- Descripción
- Computer Science Fichas sobre DS , creado por Stina Berg el 15/01/2019.
- Creado por
- Stina Berg · ene 2019
- Actualizado
- 20 abr 2019
- Visitas
- 11
- Historial
-
- Creado por Martin Myhrman · 7 ene 2019
- Copiado por TIG3RLILJA . · 13 ene 2019
- Copiado por Stina Berg · 15 ene 2019
- Valoración