  Jolfaei et al. used feedback to create transmit signals that are
simultaneously useful for multiple users in a broadcast channel. Later,
Georgiadis and Tassiulas studied erasure broadcast channels with feedback, and
presented the capacity region under certain assumptions. These results provided
the fundamental ideas used in communication protocols for networks with delayed
channel state information. However, to the best of our knowledge, the capacity
region of erasure broadcast channels with feedback and with a common message
for both receivers has never been presented. This latter problem shows up as a
sub-problem in many multi-terminal communication networks such as the
X-Channel, and the two-unicast problem. In this work, we present the capacity
region of the two-user erasure broadcast channels with delayed feedback,
private messages, and a common message. We consider arbitrary and possibly
correlated erasure distributions. We develop new outer-bounds that capture
feedback and quantify the impact of delivering a common message on the capacity
region. We also propose a transmission strategy that achieves the outer-bounds.
Our transmission strategy differs from prior results in that to achieve the
capacity, it creates side-information at the weaker user such that the
decodability is ensured even if we multicast the common message with a rate
higher than its link capacity.
