A replicated database is implemented using totally ordered reliable multicast. Clients may submit transactions to any process in the group. When process Px receives a new transaction xi from a client, it will multicast the transaction to all processes, including itself. As xi is delivered by multicast, each process submits the transaction to a local ACID database. Px returns the result (abort or commit) to the client; other processes discard the transaction result. (i) This model works well if queries do not contain the SQL time keyword, which is substituted with the current time when a transaction is evaluated. Explain why using time might be a problem and describe a solution. [4 marks] (ii) In the first release of the database, processes submit received multicast transactions synchronously, one at a time, to the local database. In a later version, to improve performance, processes are allowed to submit multiple transactions at a time asynchronously to the local database. Why does this fail to provide strong consistency for distributed transactions? Describe a solution that might allow limited (but useful) local concurrency to be supported. [3 marks] (iii) Describe changes to the design to support weak consistency, and describe two reasons why this might improve performance.

answer all

Some banks issue their Automatic Teller Machine (ATM) card customers with a randomly selected personal indentification number (PIN). Others issue their customers with an initial PIN only, and let the customers choose their own PIN the first time they use the card in an ATM. Describe the advantages and disadvantages of these approaches. [5 marks] Again, some banks compute the customer PIN by encrypting the account number using DES and a key known only to their central systems and ATMs, taking the first four hex digits of the result, replacing the digits A, . . . , F with 0, . . . , 5 respectively, and finally, if the first digit of the result is 0, replacing it with a 1. What is the probability that a criminal can get the PIN right given three guesses? [5 marks] Yet other banks have used DES, and a key known only to their central systems and ATMs, to encrypt the PIN (whether randomly generated or customer selected); they then write the result on the magnetic strip on the customer's card, so that the ATM can verify it without reference to the central system. Describe the disadvantages of this arrangement. [5 marks] In order to prevent attacks based on manipulating magnetic strips, banks in some countries have moved to using smart cards. What effect would you expect such a move to have on the incidence of card-based fraud? [5 marks] 5 [TURN OVER CST.98.12.6 7 Compiler Construction Explain how a parse-tree representation of a program may be converted into a stack-based intermediate language giving sketches of code to translate expressions, assignments and the if-then-else command; you should also explain how occurrences of a variable in an expression or assignment are translated. The program may be assumed to conform to the following syntax: E -> n | x | E + E | f(E,E) D -> let f(x,x) = {Dseq; Cseq; E} | let x = E C -> x := E; | if E then C else C Cseq -> C | C Cseq Dseq -> D | D Dseq with start symbol Dseq. Here n corresponds to integer constants, x corresponds to identifiers used as variable names and f corresponds to identifiers used as function names (you may assume these are disjoint). The function declaration construct has the effect of defining a function which, when called, makes declarations, performs commands and then returns the result of its expression; note that therefore functions may be defined within functions, but the above restriction on identifiers means that they cannot be returned as results. [20 marks] 8 Prolog for Artificial Intelligence Write Prolog programs that define the following predicates. Your programs should ensure that backtracking does not produce spurious alternative solutions. (a) The nth element of a list: nth(X,N,L) instantiates X to the Nth element of list L. Assume that list elements are numbered increasing from 1. [4 marks] (b) The last element of a list: last(X,L) instantiates X to the last element of list L. [4 marks] (c) Remove an element from a list: remove(X,L,M) instantiates M to a list containing all the elements of list L except for every occurrence of term X. [6 marks] (d) Substitute one element for another: subst(L,X,Y,M) instantiates M to a list containing all the elements of list L except that every occurrence of term X in L is replaced by term Y in M.