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);
}
}