Byzantine Gathering in Networks with Authenticated Whiteboards
説明
We propose an algorithm for the gathering problem of mobile agents in Byzantine environments. Our algorithm can make all correct agents meet at a single node in O(fm) time (f is the upper bound of the number of Byzantine agents and m is the number of edges) under the assumption that agents have unique ID and behave synchronously, each node is equipped with an authenticated whiteboard, and f is known to agents. Since the existing algorithm achieves gathering without a whiteboard in \(\tilde{O}(n^9\lambda )\) time, where n is the number of nodes and \(\lambda \) is the length of the longest ID, our algorithm shows an authenticated whiteboard can significantly reduce the time for the gathering problem in Byzantine environments.