Humberto Silva Naves

DFS – Distributed File System


Hipóteses sobre o mecanismo de comunicação:
1 - Mensagens não são geradas espontaneamente na rede;
2 - Mensagens não são maliciosamente forjadas por alguém conectado à rede;
3 - Mensagens podem ser perdidas, atrasadas, duplicadas ou recebidas em uma ordem diferente de quando foram enviadas;
4 - A rede provê um sistema de broadcast que permite o envio de uma mensagem para todos na rede;

O protocolo UDP em uma rede local LAN satisfaz todas as nossas hipóteses.

Hipoteses sobre os processadores/máquinas:
1 - Quando um processador falha ele perde todas as informações de estado anteriores. Um processador nunca pausa e retoma o trabalho depois;
2 - Não há falha do tipo Bizantina nos processadores, isto é, se o processador estiver funcionando então ele se comporta como esperado;

As hipóteses que assumimos para os processadores são bastante realistas para o nosso ambiente.

Variáveis de estado:

- Status: Pode ser dentre DOWN, RECOVERY, MERGE, ELECTION, REORGANIZATION e NORMAL;
- Group: número do grupo (deve ser gerado de forma a nunca repetir) do processador
- Id: Identificação do processador
- Coordinator: Identificação do coordenador do grupo;
- IsCoordinatorAlive: variável booleana para checagem se o coordenador ainda está vivo;


Mensagens trocadas:

1 - AreYouCoordinator[From]
  Essa mensagem é enviada via broadcast para todos os membros da rede perguntando se algum deles é coordenador de algum grupo;
  Parâmetros
  - From: o remetente da mensagem;
  
2 - AreYouCoordinatorReply[From, To, Reply]
  Essa mensagem é uma resposta à mensagem "AreYouCoordinator"
  Parâmetros:
  - From: o remetente da mensagem;
  - To: o destinatário da mensagem;
  - Reply: Sim ou não, dependendo se o remetente é ou não é um coordenador;

3 - AreYouThere[From, To, Group]
  Essa mensagem é enviada por um dos membros de um grupo para o respectivo coordenador perguntando se o coordenador está ainda vivo e se continua como coordenador do grupo "Group";
  Parâmetros:
  - From: o remetente;
  - To: o destinatário;
  - Group: o grupo em questão;
  
4 - AreYouThereReply[From, To, Reply]
  Resposta à mensagem "AreYouThere"
  Parâmetros:
  - From: o remetente;
  - To: o destinatário;
  - Reply: Sim ou não, dependendo se o remetente ainda é coordenador do grupo da mensagem "AreYouThere";

5 - Invitation[To, GroupCoordinator, Group]
  Convida algum processador para entrar no grupo "Group" cujo coordenador é "GroupCoordinator".
  Parâmetros:
  - To: o destinatário da mensagem;
  - GroupCoordinator: o coordenador do novo grupo;
  - Group: o novo grupo;
  
6 - Accept[From, To, Group]
  Confirma a entrada do membro em um grupo.
  Parâmetros:
  - From: o remetente;
  - To: o destinatário da mensagem, que deve ser o coordenador do grupo;
  - Group: o grupo em questão;
  
7 - AcceptReply[From, To, Reply]
  Dá um acknowledge que recebeu reply e que foi confirmado no grupo.
  Parâmetros:
  - From: o remetente;
  - To: o destinatário;
  - Reply: Sim ou não, dependendo se o "Accept" foi aceito ou não;

8 - Ready[From, To, Group, Definition]
  Começa a computação de "Definition"
  Parâmetros:
  - From: o remetente;
  - To: o destinatário;
  - Group: o grupo em questão;
  - Definition: a definição do problema a ser calculado;

9 - ReadyReply[From, To, Group, Reply]
  Reposta à mensagem "ReadyReply".
  Parâmetros:
  - From: o remetente;
  - To: o destinatário;
  - Group: o grupo em questão;
  - Reply: Sim ou não, dependendo se o "Ready" foi aceito ou não;


Dinâmicas:  

1 - Dinâmica do "AreYouThere":

 A dinâmica do "AreYouThere" é semelhante a dinâmica do "ping" que de tempos em tempos pergunta se o coordenador do grupo está vivo. O processador comum que não é o coordenador do seu grupo, de tempos em tempos, envia a mensagem AreYouThere e espera por um período de tempo pré-determinado. Se não ouver resposta do coordenador em tempo hábil, o processador comum entra em estado de RECOVERY.
 
 (Id=A,Group=G,Coordinator=X)
       Processador A                                      Processador X 
            | AreYouThere[From=A,To=X,Group=G]                 |
            | ------------>                                    |
            |                                                  |
            |          AreYouThereReply[From=X,To=A,Reply=Yes] |
            |                                <---------------- |
            |                                                  |
            |                                                  |

Timeout() {
  if (Status != NORMAL || Coordinator == Id) return;
  Send(AreYouThere[From=Id, To=Coordinator, Group=Group]);
  IsCoordinatorAlive = false;
  Wait(ARE_YOU_THERE_TIMEOUT);
  if (IsCoordinatorAlive == false) {
    Status = RECOVERY;
  }
}

OnReceiveAreYouThere(AreYouThere Message) {
  if (Message.Group == Group && Coordinator == Id) {
    Send(AreYouThereAnswer[From=Id, To=Message.From, Reply=true]);
  } else {
    Send(AreYouThereAnswer[From=Id, To=Message.From, Reply=false]);
  }
}

OnReceiveAreYouThereReply(AreYouThereReply Message) {
  if (Id != Coordinator) {
    IsCoordinatorAlive = Message.Reply;
  }
}


2 - Dinâmica do "AreYouCoordinator":
 A dinâmica do "AreYouCoordinator" serve para descobrir outros coordinator que estão na mesma rede;
 
 (Id=A,Group=G,Coordinator=A)
       Processador A                                           Processador X 
            | AreYouCoordinator[From=A] (broadcast)                  |
            | ------------>                                          |
            |                                                        |
            |          AreYouCoordinatorReply[From=X,To=A,Reply=Yes] |
            |                                      <---------------- |
            |                                                        |
            |                                                        |
            
Discovery() {
  if (Status != NORMAL || Id != Coordinator) return;
  OtherCoordinators = EMPTY;
  Send(AreYouCoordinator[From=Id]);
  Wait(DISCOVERY_TIMEOUT);

  Wait(Random())??
  
  if (OtherCoordinators not empty && Status == NORMAL) {
    Status = MERGE;
  }
}

OnReceiveAreYouCoordinator(AreYouCoordinator Message) {
  if (Status == NORMAL && Id == Coordinator) {
    Send(AreYouCoordinatorReply[From=Id, To=Message.From, Reply=true]);
  } else {
    Send(AreYouCoordinatorReply[From=Id, To=Message.From, Reply=false]);
  }
}

OnReceiveAreYouCoordinatorReply(AreYouCoordinatorReply Message) {
  if (Message.Reply == true) {
    OtherCoordinators.add(Message.From);
  }
}