CS417 Exam 1

Fall 2016

Paul Krzyzanowski

Part I – 24 Points

4 points
Why does it not make sense to use TCP (Transmission Control Protocol) for the Network Time Protocol (NTP)?
4 points
What is a benefit of lease-based garbage collection over reference count based garbage collection?
6 points
(a) Explain the role of an interface definition language in remote procedure calls.
(b) Explain the purpose of marshaling in remote procedure calls.
4 points
A client requests time from a server. It takes 80 ms (0.080 seconds) to get the response, which contains a timestamp of 5:23:30.000. Using Cristian?s algorithm, to what time does the client set its clock?
6 points

The diagram shows three multicasts to a group of three processes. The sending of each multicast message is a single event.
(a) Assign vector timestamps to each event using a sequencing of (P₀, P₁, P₂). The first event on each process gets a sequence number of 1.
(b) Based on the vector clock values, which events are concurrent with event b?

Part II – 60 points – 3 points each

For each statement, select the most appropriate answer.

Metcalfe's Law, named after the inventor of Ethernet, tells us that the value of a network increases as:
(a) The speed of the network increases.
(b) The cost of networking hardware decreases.
(c) The amount of data sent per person increases.
(d) The number of connected users increases.
A directory in a cache coherent NUMA architecture is:
(a) A tree-structured mapping of processes to processors.
(b) A per-processor table that keeps track of which other processors have cached copies of regions of memory.
(c) A global structure that enables the operating system to switch the connections of processors to memory.
(d) A listing of files that are accessible by each processor.
A snoopy cache can speed up:
(a) Memory reads.
(b) Memory writes.
(c) Both memory reads and writes.
(d) Neither memory reads or writes.
Ethernet communication uses:
(a) Time division multiplexing.
(b) Frequency division multiplexing.
(c) Channel access via token passing.
(d) Random access.
IP is designed to be implemented over:
(a) Unreliable connectionless networks.
(b) Reliable connectionless networks.
(c) Unreliable connection-oriented networks.
(d) Reliable connection-oriented networks.
Port numbers are used in:
(a) IP.
(b) UDP only.
(c) UDP & TCP.
(d) TCP only.
TCP cannot provide
(a) Reliable delivery.
(b) In-order delivery.
(c) Constant latency.
(d) Congestion control.
To enable a TCP socket to receive incoming connections, the following system call should be used:
(a) bind
(b) listen
(c) accept
(d) recvfrom
An idempotent function:
(a) Is any function that can accept parameters in a serialized format.
(b) Can be stored in byte code format and downloaded by a client.
(c) Is a remote function rather than a local function.
(d) Can be called multiple times without side-effects.
A key advantage of multi-canonical marshaling is that it:
(a) Enables a set of data to be sent to multiple servers simultaneously.
(b) Allows clients and servers to have different processor architectures.
(c) Reduces the overall amount of data conversion that needs to be performed.
(d) Allows clients to communicate directly with servers without routing messages through a proxy.
DCE RPC improved ONC (Sun) RPC by adding:
(a) An interface definition language.
(b) A cell directory server to look up RPC services.
(c) Support for distributed objects.
(d) An RPC compiler (stub generator).
A surrogate process in Microsoft?s COM+:
(a) Runs on the client and loads client-side stub objects.
(b) Runs on the client and receives requests if the server cannot be reached.
(c) Runs on the server and starts RPC services at boot time.
(d) Runs on the server and loads objects based on client requests.
In a group of two computers, a client?s local clock reads 6:27:10. Using the Berkeley clock synchronization algorithm, to what value does the client set its time if the server?s clock reads 6:28:30? Ignore message transit times.
(a) 6:27:50
(b) 6:28:30
(c) 6:29:10
(d) 6:29:50
An NTP synchronization subnet is:
(a) A high-speed network that is dedicated to clock synchronization.
(b) The set of servers that offers clock synchronization services.
(c) Reserved capacity dedicated to clock synchronization in an existing network.
(d) Any network over which an NTP server continuously sends time broadcasts.
With the use of Lamport timestamps, we can achieve:
(a) Global ordering.
(b) Total ordering.
(c) Partial ordering.
(d) Sync ordering.
Atomic multicast differs from reliable multicast because atomic multicast:
(a) Is much faster since it uses the network hardware to ensure reliability.
(b) Only requires partial ordering.
(c) Does not need to deliver messages reliably.
(d) Accounts for system failures.
Lamport's mutual exclusion algorithm is an example of a:
(a) Centralized algorithm.
(b) Token-based algorithm.
(c) Contention-based algorithm.
(d) Random-selection algorithm.
Which mutual exclusion algorithm does not require knowledge of group members?
(a) Centralized.
(b) Token ring.
(c) Lamport.
(d) Ricart and Agrawala.
The Chang & Roberts ring algorithm improves the ring election algorithm by:
(a) Stopping redundant elections when possible.
(b) Using a centralized coordinator to decide on election results.
(c) Using total ordering of election messages.
(d) Using reliable message delivery.
The Bully election algorithm chooses:
(a) The first process to notice a dead leader.
(b) The highest living process ID.
(c) The process that sends the most election messages during the election.
(d) The process that gets the majority consensus from the group.

Part III – 14 points – 2 points each

For each statement, answer True (T) or False (F).

On multiprocessor systems, processors share a system clock.
A switched network connection enables greater scalability than a bus-based one.
Ethernet transmission is unreliable.
TCP is a network-layer (layer 3) protocol.
Explicit typing identifies the data elements in a message.
If the Lamport timestamp associated with event A is less than the Lamport timestamp associated with event B, we can conclude that event A happened before event B.
Unlike SNTP, with PTP (Precision Time Protocol) the server initiates clock synchronization.
A hold-back queue is used to resequence messages at the receiver.