# ASD 2014/2015

## Test 2, 2012



### Questão 1.

#### a

* a1 - `V`
* a2 - `V`
* a3 - `F` - O Paxos não garante Liveness
* a4 - `F` 
* a5 - `V`

#### b


(image missing, will be present on next update)


#### c

![1b](img/asd_1b.png =x300)


### Questão 2.

#### (a)

Sim.

![1b](img/asd_2a.png =x300)


#### (b)

Não.

![1b](img/asd_2b.png =x300)

```
24 < 36
36 < 95

Mas 24 ~< 95 => impossível
```

#### (c)

Sim.

![1b](img/asd_2c.png =x350)


### Questão 3.

#### (a)

(segundo o professor, apenas C)

* **C** 

#### (b)

> Amazon Dynamo, in contrast, provides AP because the system is always available if any replica is up and reachable, even in a partition, but might not be consistent, even without a partition. Dynamo provides eventual consistency approximation instead of a consistency guarantee.

* **A**
* **P**


### Questão 4.

![4](img/asd_4.png =x300)

`m = 5`

#### (a)

Tabela de *fingers* do nó `20` :

O finger `i` é dado por `succ( (20 + 2^{i-1}) % 2^m ) , i = 1..m`

| `i` | `finger[i]` |
|:---:|:-----------:|
| `1` | `succ((20 + 1) 	% 32 ) = succ(21) 	= 23`  |
| `2` | `succ((20 + 2) 	% 32 ) = succ(22) 	= 23`  |
| `3` | `succ((20 + 4) 	% 32 ) = succ(24) 	= 25`  |
| `4` | `succ((20 + 8) 	% 32 ) = succ(28) 	= 30`   |
| `5` | `succ((20 + 16) 	% 32 ) = succ(4) 	= 5`  

#### (b)

`20.lookpup(13)`

Maior *finger* que precede `13`: `finger[5] = 5`

Tabela de *fingers* do nó `5` :

| `i` | `finger[i]` |
|:---:|:-----------:|
| `1` | `succ((5 + 1) 	% 32 ) = succ(6) 	= 10`  |
| `2` | `succ((5 + 2) 	% 32 ) = succ(7) 	= 10`  |
| `3` | `succ((5 + 4) 	% 32 ) = succ(9) 	= 10`  |
| `4` | `succ((5 + 8) 	% 32 ) = succ(13) 	= 17`  |
| `5` | `succ((5 + 16) 	% 32 ) = succ(21) 	= 23`  |


Maior *finger* que precede `13`: `finger[{1..3}] = 10`

Tabela de *fingers* do nó `10` :

| `i` | `finger[i]` |
|:---:|:-----------:|
| `1` | `succ((10 + 1) 	% 32 ) = succ(11) 	= 12`  |
| `2` | `succ((10 + 2) 	% 32 ) = succ(12) 	= 17`  |
| `3` | `succ((10 + 4) 	% 32 ) = succ(14) 	= 17`  |
| `4` | `succ((10 + 8) 	% 32 ) = succ(18) 	= 20`  |
| `5` | `succ((10 + 16) 	% 32 ) = succ(26) 	= 30`  |

Maior *finger* que precede `13`: `finger[1] = 12`

Como a chave se situa entre o `12` e o seu sucessor, `17`, paramos.

`20.loopkup(13) =  20 -> 5 -> 10 -> 12 -> 17`



#### (c)

Uma estratégia possível era manter mais um atributo na tabela de fingers, contendo o RTT desse finger. Ao seleccionar um finger, se o seu RTT excedesse um dado threshold, seria escolhido um finger menor (um shortcut que ficasse mais longe). Isto não altera a correcção, uma vez que não muda o critério sobre o qual os fingers são escolhidos. Apenas poderá incorrer num maior número de hops.


### Questão 5.

* `F`
* `V`
* `F`