  We study the task of Byzantine gathering in a network modeled as a graph.
Despite the presence of Byzantine agents, all the other (good) agents, starting
from possibly different nodes and applying the same deterministic algorithm,
have to meet at the same node in finite time and stop moving. An adversary
chooses the initial nodes of the agents and assigns a different label to each
of them. The agents move in synchronous rounds and communicate with each other
only when located at the same node. Within the team, f of the agents are
Byzantine. A Byzantine agent acts in an unpredictable way: in particular it may
forge the label of another agent or create a completely new one. Besides its
label, which corresponds to a local knowledge, an agent is assigned some global
knowledge GK that is common to all agents. In literature, the Byzantine
gathering problem has been analyzed in arbitrary n-node graphs by considering
the scenario when GK=(n,f) and the scenario when GK=f. In the first (resp.
second) scenario, it has been shown that the minimum number of good agents
guaranteeing deterministic gathering of all of them is f+1 (resp. f+2). For
both these scenarios, all the existing deterministic algorithms, whether or not
they are optimal in terms of required number of good agents, have a time
complexity that is exponential in n and L, where L is the largest label
belonging to a good agent.
  In this paper, we seek to design a deterministic solution for Byzantine
gathering that makes a concession on the proportion of Byzantine agents within
the team, but that offers a significantly lower complexity. We also seek to use
a global knowledge whose the length of the binary representation is small.
Assuming that the agents are in a strong team i.e., a team in which the number
of good agents is at least some prescribed value that is quadratic in f, we
give positive and negative results.
