  We consider the problem of finding a maximal independent set (MIS) in the
shared blackboard communication model with vertex-partitioned inputs. There are
$n$ players corresponding to vertices of an undirected graph, and each player
sees the edges incident on its vertex -- this way, each edge is known by both
its endpoints and is thus shared by two players. The players communicate in
simultaneous rounds by posting their messages on a shared blackboard visible to
all players, with the goal of computing an MIS of the graph. While the MIS
problem is well studied in other distributed models, and while shared
blackboard is, perhaps, the simplest broadcast model, lower bounds for our
problem were only known against one-round protocols.
  We present a lower bound on the round-communication tradeoff for computing an
MIS in this model. Specifically, we show that when $r$ rounds of interaction
are allowed, at least one player needs to communicate $\Omega(n^{1/20^{r+1}})$
bits. In particular, with logarithmic bandwidth, finding an MIS requires
$\Omega(\log\log{n})$ rounds. This lower bound can be compared with the
algorithm of Ghaffari, Gouleakis, Konrad, Mitrovi\'c, and Rubinfeld [PODC 2018]
that solves MIS in $O(\log\log{n})$ rounds but with a logarithmic bandwidth for
an average player. Additionally, our lower bound further extends to the closely
related problem of maximal bipartite matching.
  To prove our results, we devise a new round elimination framework, which we
call partial-input embedding, that may also be useful in future work for
proving round-sensitive lower bounds in the presence of edge-sharing between
players.
  Finally, we discuss several implications of our results to multi-round
(adaptive) distributed sketching algorithms, broadcast congested clique, and to
the welfare maximization problem in two-sided matching markets.
