NOTE:
COMPSCI 711 THE UNIVERSITY OF AUCKLAND
SEMESTER TWO 2016 Campus: City
COMPUTER SCIENCE Parallel and Distributed Computing
(Time Allowed: TWO hours)
Attempt ALL questions.
Page 1 of 5
Question 1
(a) What is the most important difference between the totally ordered logical clock and the partially ordered logical clock?
(b) Use a detailed example to explain why it is more desirable to use the partially ordered logical clock for some applications.
(c) Compare and contrast the partially ordered logical clock and the totally ordered logical clock in terms of expressiveness and scalability. You must provide sufficient justification for your answer.
(10 marks)
Question 2
(a) Explain how a Bitcoin transaction works and how the Bitcoin network ensures that a user’s Bitcoin is not spent by other people.
(b) What is the purpose for having a block chain in the Bitcoin network?
(c) Describe the mechanism that the Bitcoin network uses to reach consensus on which blocks are in the block chain. In your description, you should explain what a valid block
is and discuss the likelihood of conflicts and how conflicts are resolved.
(d) Discuss how the security of the block chain, the diversity of the Bitcoin network miners
and the value of the bitcoin influence each other.
Question 3
(18 marks)
(a) Explain state machine replication.
(b) What is virtual synchrony? In your description, you should explain the meaning of group
view, view change and the property/properties that a multicast message needs to satisfy.
(c) Assume that the data of an application are replicated on several data centers. The machines in the data centers are susceptible to fail-stop failures. The machines can fail at any time, even during a view change. Outline an algorithm that ensures virtual synchrony
amongst the data centers hosting the data of the application.
(i) Youshouldbrieflydescribethebasicprinciplesofyourimplementation.
(ii) You should give sufficient explanations for each statement and the symbols used
in the detailed descriptions of your algorithm.
(iii)You should explain why your algorithm ensures virtual synchrony.
Page 2 of 5
COMPSCI 711
(22 marks)
Question 4
(a) What is the goal of the distributed Bellman-Ford algorithm, what does it try to achieve
(DFS, BFS, MST, or otherwise)?
(b) Discuss the exponential message complexity of the asynchronous Bellman-Ford algorithm. Base your discussion on a sample diagram as used in the lectures (see the figure below).
(c) Based on (b), discuss how the time complexity can also be exponential, in the FIFO scenario.
(d) Propose sample message delivery times for the slow links, as integer values, compatible with the arguments discussed at (b).
(e) Discuss why the same arguments cannot be applied to the synchronous Bellman-Ford algorithm. Consider that an asynchronous link x z which takes two (2) time units can be simulated by a sequence of two (2) synchronous links x y z, by inserting a new node y. Why such a simulation of slow links – in our scenario the horizontal links in the figure – will not induce an exponential message complexity in the synchronous case?
(20 marks)
COMPSCI 711
Page 3 of 5
Question 5
Discuss and sketch the thought experiment proof of the impossibility of deterministically solving the synchronous Byzantine problem when N ≤ 3F. Assume that we already proved the base cases N=2 and N=3 and now we need to extend the proof for larger N’s. You may base your arguments on diagrams similar to the lectures notes, reproduced below. Ensure that you discuss the following items:
(a) Proof by contradiction and initial work hypothesis
(b) Construction details (combined “super” nodes, combined channels)
(c) How the “super” nodes work, including their initialisation and their termination (d) The final contradiction and its conclusion
(15 marks)
COMPSCI 711
Page 4 of 5
Question 6
(a) Discuss the relation of the distributed synchronous MST algorithm and the classical
Prim, Kruskal and Boruvka algorithms.
(b) Demonstrate your understanding by illustrating its evolution using the scenario indicated by the figure below. Nodes have unique integer node IDs and edges have weights that are not all distinct!
(c) While describing this evolution, discuss which edges are chosen as MWOE’s and which nodes are chosen as roots – justify your choices
(d) Discuss and justify the time complexity of the distributed synchronous MST.
________________________________________
Page 5 of 5
COMPSCI 711
(15 marks)