Sincronismo Parcial Unificado

A literatura sobre computação distribuída considera múltiplas opções para modelar a comunicação. De maneira mais simples, a comunicação é categorizada como síncrona ou assíncrona. A comunicação síncrona assume que as mensagens são entregues dentro de um intervalo de tempo publicamente conhecido e que os relógios das partes estão sincronizados. A comunicação assíncrona, por outro lado, assume apenas que as mensagens serão entregues eventualmente. Uma abordagem mais sutil, ou um meio termo entre os dois extremos, é dada pelo modelo parcialmente síncrono, que é, sem dúvida, a opção mais realista. Este modelo vem em duas variantes comumente consideradas: (i) O modelo de Tempo de Estabilização Global (GST): após um período de tempo (desconhecido), a rede se torna síncrona. Isso captura cenários onde os problemas de rede são transitórios. (ii) O modelo de Latência Desconhecida (UL): a rede é, de fato, síncrona, mas o limite de delay da mensagem é desconhecido. Este trabalho estabelece formalmente que qualquer propriedade indiferente ao tempo que pode ser alcançada por um protocolo no modelo UL também pode ser alcançada por um protocolo (possivelmente diferente) no modelo GST. Por indiferente ao tempo, queremos dizer propriedades que podem depender da ordem em que os eventos ocorrem, mas não do tempo medido pelas partes. A maioria das propriedades consideradas em computação distribuída são indiferentes ao tempo. O inverso já era conhecido, mesmo sem o requisito de indiferença ao tempo, portanto nosso resultado mostra que as duas condições de rede são, sob uma suposição sensata, igualmente exigentes.