# What do these lower bounds really mean?

I was reading an abstract for a paper that gives a minimum number M of good agents that guarantees f-Byzantine gathering, if there are f Byzantine agents. It gives a lower bound of f+1 for strongly byzantine agents. It also says that:

"...we give deterministic gathering algorithms for at least 2f+1 good agents when the size of the network is known...".

There are two lower bounds to the number of good agents. What do those two lower bounds mean? If it was only one lower bound, it would have been clear.

The abstract is: Gathering Despite Mischief

## 1 Answer

Note that the paper considers strongly Byzantine agents and weakly Byzantine agents. From the abstract:

For weakly Byzantine agents, we show that any number of good agents permits solving the problem for networks of known size. If the size is unknown, then this minimum number is f+2. More precisely, we show a deterministic polynomial algorithm that gathers all good agents in an arbitrary network, provided that there are at least f+2 of them. We also provide a matching lower bound: we prove that if the number of good agents is at most f+1, then they are not able to gather deterministically with termination in some networks.

So for $f$ weakly Byzantine agents any number of good agents will do if the network size is known. Alternatively if it is not known, $\ge f+2$ good agents is a lower bound and they also show the matching upper bound.

For strongly Byzantine agents, we give a lower bound of f+1, even when the graph is known: we show that f good agents cannot gather deterministically in the presence of f Byzantine agents even in a ring of known size. On the positive side, we give deterministic gathering algorithms for at least 2f+1 good agents when the size of the network is known and for at least 4f+2 good agents when it is unknown.

In the strongly Byzantine case, they show that $f+1$ is a lower bound on the number of good agents required when the network size is known, which implies that this is true when the network size is unknown. These lower bounds aren't tight it seems as their best algorithms require $\ge 2f+1$ good agents in the case where the network size is known, or $\ge 4f+2$ good agents if the network size is unknown.

• Shouldn't an upper bound be the most an algorithm can reach? But in this case, their best algorithms require "more than or equal t " 2f +1 agents for a known size not "less than or equal to" 2f +1 agents. That does not sound like an upper bound but a lower bound. I'm confused. – Manuel Nov 9 '15 at 20:31
• Yes just corrected that. – Peter Nov 13 '15 at 10:49