Approximate distributed agreement toolkit

Abstract

Distributed Agreement is a well known and researched problem, one whose solutions have vast application in Distributed Systems, as reaching agreement over a certain value or over the order of received messages is extremely important in many multi-agent contexts. Approximate agreement has long been relegated to the sidelines compared to exact agreement, with its most notable application being clock synchronisation. Other proposed applications stemming from control theory target multi-agent consensus, namely for sensor stabilisation, coordination in robotics, and trust estimation. Several proposals for approximate agreement follow the Mean-Subsequence-Reduce approach, simply applying different functions at each phase. However, taking clock synchronisation as an example, applications do not fit neatly into each generic algorithm’s definition: instead they require adapting their internals. Our contribution is three-fold. First, we conduct a survey on approximate agreement and related algorithms, delineating their characteristics thoroughly. Second, we identify additional configuration points, establishing a more general template of MSR approximate agreement algorithms. We then show how this allows us to implement not only generic algorithms but also those tailored for specific purposes. Finally, we propose a toolkit for making approximate agreement practical, providing classical implementations as well as allow these to be configured for specific purposes. We validate the implementation with classical algorithms and clock synchronisation.

Acordo Distribuído é um problema bem conhecido e estudado, com soluções de vasta aplicabilidade em Sistemas Distribuídos, uma vez que atingir acordo sobre um certo valor ou sobre a ordem de mensagens recebidas é extremamente importante em muitos contextos multi-agente. Acordo Aproximado tem sido relegado a segundo plano em comparação a acordo exato, sendo a sua aplicação mais notória sincronização de relógios. Outras aplicações propostas, provenientes da teoria de controlo, visam o consenso multi-agente, nomeadamente para a estabilização de sensores, coordenação robótica e estimativa de confiança. Várias propostas de algoritmos de acordo aproximado seguem a abordagem Mean-Subsequence-Reduce, simplesmente aplicando várias funções de aproximação em cada fase. No entanto, utilizando sincronização de relógios como exemplo, aplicações não encaixam perfeitamente na definição dos algoritmos genéricos: é necessário adaptá-los. A nossa contribuição é constituída por três partes. Primeiramente, realizamos uma sondagem sobre acordo aproximado e algoritmos relacionados, delineando minuciosamente as suas características. Em segundo lugar, identificamos pontos de configuração adicionais, estabelecendo um esqueleto de algoritmos de acordo aproximado MSR. Demonstramos então como é que isto nos permite implementar não só algoritmos genéricos, como também aqueles adaptados a propósitos específicos. Finalmente, propomos um conjunto de ferramentas para passar acordo aproximado à prática, incluindo implementações de algoritmos clássicos, bem como a possibilidade de implementar mais algoritmos para propósitos específicos. Validamos então a implementação com algoritmos clássicos e com sincronização de relógios.