You are an expert at summarizing long articles. Proceed to summarize the following text: 
a fundamental question of communication theory is : at what rate can information be transmitted reliably over a noisy channel ? there is more than one way to go about answering this question . for instance , consider an erasure channel where the parameter @xmath0 denotes the probability with which a transmission on the channel is lost ; with probability @xmath1 the transmission is received without error . the traditional approach for describing the rate of reliable communication for the erasure channel is to cite its shannon capacity , which is @xmath1 bits per channel use for a channel with binary inputs and outputs . if feedback is available to notify the sender when a channel input is erased , then the capacity can be achieved by retransmitting lost inputs @xcite . alternatively , the rate of reliable communication can be described by the _ maximum stable throughput_. in this setting , we view the channel input as a packet of fixed length that arrives at a random time to a sender and is stored in an infinite - capacity buffer while awaiting its turn to be sent over the channel . the packets in the buffer form a queue that is emptied in a specified order , traditionally in first - in - first - out ( fifo ) order . a transmission protocol , for instance an automatic repeat request ( arq ) protocol , provides a form of redundancy to ensure that the packet is received correctly . the maximum stable throughput is the highest rate ( in packets per channel use ) at which packets arrive to the sender while ensuring that the queue remains finite . in the case of the erasure channel , if we assume that packets arrive to the sender according to a bernoulli process , feedback is available to notify the sender of lost packets , and the transmission protocol consists of retransmitting lost packets , then the buffer at the sender forms a discrete - time @xmath2 queue with maximum departure rate @xmath1 . the maximum stable throughput is @xmath1 , which is identical to the shannon capacity .    for _ multiuser systems _ , the relation between the shannon capacity and the maximum stable throughput for communication over an erasure channel has been explored in the context of random multiple access , where user @xmath3 transmits with probability @xmath4 at each transmission opportunity . this form of random channel access is a variation on abramson s aloha protocol @xcite and is particularly attractive for use in mobile ad - hoc networks because it is robust to variations in the network topology and can be implemented without coordination among the transmitting nodes . the finite - user , buffered random access problem was first formulated by tsybakov and mikhailov @xcite , who provided a sufficient condition for stability and thus a lower bound on the maximum stable throughput . the problem they considered was a system in which finitely many source nodes with infinite - capacity queues randomly access a shared channel to send messages to a central station . feedback was used to notify the source nodes of failed transmissions and a retransmission scheme was used to ensure eventual successful reception at the central station . the users were assumed to access a _ collision channel _ , in which transmission by more than one source results in the loss of all transmitted packets with probability 1 . this collision channel model is equivalent to an erasure channel , where for user @xmath3 , @xmath5 . further progress on this problem was made in @xcite , in which stochastic dominance arguments were explicitly introduced to find the stable throughput region for a system with 2 source nodes , and in @xcite , wherein a stable throughput region based on the joint queue statistics was found for 3 source nodes . an exact stability result for arbitrarily ( but finitely ) many users has not been found , but bounds have been obtained in @xcite and @xcite . recently , the authors of @xcite improved upon the collision channel model used in all previous works and studied a channel with multipacket reception ( mpr ) capability . they showed that the stable throughput region transfers from a non - convex region under the collision channel model to a convex region bounded by straight lines for a channel with mpr . the shannon capacity region of a random access system was considered in @xcite and @xcite , which both obtained the capacity region for finitely many source nodes transmitting to a central station under the collision channel model . that capacity result can be viewed as the capacity of an asynchronous multiple access channel , which was obtained in @xcite and @xcite . the more recent contribution of @xcite shows explicitly how the random access capacity region in @xcite is obtained from the results in @xcite , in addition to analyzing the capacity for a channel in which packets involved in a collision can be recovered . it was noted by massey and mathys @xcite and rao and ephremides @xcite that the stable throughput and shannon capacity regions coincide for the special cases of two source nodes and infinitely - many source nodes . as with the point - to - point erasure channel , this result is surprising in that it suggests that the bursty nature of arriving packets , which is captured in the stability problem but not in the capacity problem , is immaterial in determining the limits on the rate of reliable communication . it has been conjectured that the stable throughput region for finitely - many source nodes transmitting to a central station ( which is an unsolved problem ) coincides with the corresponding capacity region . this conjecture was explored in @xcite , in which it was shown to hold in a special case involving correlated arrivals of packets at the source nodes . recently , further progress was made in @xcite towards showing that the stable throughput and shannon capacity regions coincide for transmission over a channel with mpr . however , a complete proof has still not been found .    in this work we explore the relation between the stable throughput and shannon capacity for a random access system in which source nodes _ multicast _ their messages to multiple receivers . specifically , we consider a system with two source nodes and two destination nodes . the source nodes randomly access the channel to transmit to the two destination nodes . we first characterize the shannon capacity region of the system , which is similar to ahlswede s result @xcite on the capacity for two senders and two receivers . we then move to the queueing stability problem and characterize the stable throughput region for our random access multicast system with two different transmission policies . the first is a retransmission policy , which is the policy used in previous works on queueing stability for a ( single ) central station . next , we study random access multicast with random linear coding , which is inspired by the recent development of network coding @xcite and fountain coding @xcite . our results show that for multicast transmission , the maximum stable throughput under the retransmission policy does not reach the shannon capacity , however , the random linear coding scheme provides a maximum stable throughput that asymptotically approaches the shannon capacity . , the reception probabilities are as shown above.,scaledwidth=30.0% ]    the system we consider throughout this work is shown in fig . [ fig : general_2sour2dest ] . two source nodes , indexed by @xmath3 , each generate messages to be multicast to two destination nodes , indexed by @xmath6 , over a shared channel . the data generated at source @xmath7 is assumed independent of the data generated at source @xmath8 . time is slotted ; one time slot corresponds to the amount of time needed to transmit a single packet over the shared channel . a packet is a fixed - length vector of bits . in each time slot , if source @xmath3 has a packet to transmit , then we refer to the source as being _ backlogged _ ; otherwise the source is _ empty_. a backlogged source transmits in a slot with probability @xmath4 . we refer to @xmath4 as the transmission probability ; it encapsulates random access to the channel . we assume the value of @xmath4 to be fixed in time . ( i.e. , we do not assume retransmission control , in which @xmath4 is varied over time according to the history of successful transmissions . ) the channel model we consider is similar to the model used in @xcite . a transmitted packet is received without error with a certain probability . otherwise , the packet is lost and can not be recovered . we assume that the channels between different source - destination pairs are independent . we introduce the following _ reception probabilities _ for sources @xmath9 and destinations @xmath10 . @xmath11 @xmath12 we assume throughout that interference can not increase the reception probability on the channel , i.e. , @xmath13 . the reception probabilities inherently account for interference and also allow for multipacket reception ( mpr ) . note that these probabilities can capture the effects of fading on the wireless channel by setting them equal to the probability that a fading signal , represented by a random variable , exceeds a certain signal to interference plus noise ( sinr ) threshold . the collision channel model used in a number of previous works is given by @xmath14 , @xmath15 . we first analyze the system under consideration in an information - theoretic framework to determine the shannon capacity region . thus we assume in this section that the sources are always backlogged . coding is performed on the data at the source nodes , and we view each transmitted packet as a codeword symbol , where a collection of @xmath16 codeword symbols constitutes a codeword . in order to allow for random access of the channel , we assume that while codeword symbols are synchronized ( equivalently , time is slotted ) , the codewords for the two sources do not necessarily begin and end in the same time slots . we analyze this system first for a general discrete memoryless channel ( dmc ) and then apply our random access channel model to obtain the capacity region . the discrete memoryless channel we consider consists of discrete alphabets @xmath17 and @xmath18 and transition probability matrix @xmath19 . the channel can be decomposed into two multiple access channels , each corresponding to a destination node and defined as follows . @xmath20 we assume that there is no feedback available on the channel , which differs from the assumption made in the model for the stable throughput problem presented in section [ section : stablethroughputregion ] . source node @xmath3 generates a sequence of messages @xmath21 where the @xmath22 message @xmath23 takes values from the message set @xmath24 . the messages are chosen uniformly from @xmath24 and independently over @xmath3 . the encoding function @xmath25 at source @xmath3 is given by the mapping @xmath26 the encoder output consists of a sequence of codewords @xmath27 , @xmath28 . the system is asynchronous in the following sense . each source and each destination maintain a clock . let @xmath29 denote the amount of time that the clock at source @xmath3 is running ahead of the clock at destination @xmath6 . the @xmath29 are assumed to be integers , meaning that time is discrete and transmissions are symbol - synchronous . the time at each clock can be divided into _ periods _ of length @xmath16 corresponding to the length of a codeword . let @xmath30 denote the offset between the start of periods at source @xmath3 and destination @xmath6 , where @xmath31 . we assume that @xmath30 are uniform over @xmath32 $ ] for all @xmath16 . the codeword @xmath33 is sent at time @xmath34 on the clock at source @xmath3 . a sequence of channel outputs are observed at each destination , where the outputs at destination @xmath6 each take values from the alphabet @xmath35 . the decoder operates on a sequence of @xmath36 channel outputs to form an estimate of a sequence of @xmath37 messages . a decoder is defined as follows . @xmath38 where @xmath39 denotes the @xmath40-fold cartesian product of @xmath41 . since the decoder must synchronize on a particular source @xmath3 , the decoding function is defined separately for each source . the output of the decoder is a sequence of message estimates @xmath42 , where @xmath43 denotes the estimate at destination @xmath6 of the @xmath22 message sent by source @xmath3 . the error criterion we consider is the average probability of error @xmath44 defined as @xmath45 the rate pair @xmath46 is _ achievable _ if there exists encoding functions @xmath47 and decoding functions @xmath48 such that @xmath49 for all @xmath50 as @xmath51 . the capacity region is the set of all achievable rate pairs    the model we consider here is a compound version of the _ totally asynchronous multiple access channel _ treated in @xcite and @xcite . as shown in those works , the asynchrony in the system results in the lack of a convex hull operation , and this holds as well in our compound version of the problem . the capacity region is presented below and the proof of the theorem is described in appendix [ app : proofcapreg ] . the capacity region of the asynchronous compound multiple access channel is the closure of all rate points @xmath52 that lie in the region @xmath53[c]{c } \bigcap_{m } \left\{(r_1,r_2):\begin{ieeeeqnarraybox}[\relax][c]{r'l'l } r_1 & \!\ ! < \!\ ! & i(x_1;y_m | x_2 ) \\ r_2 & \!\ ! < \!\ ! & i(x_2;y_m r_1+r_2 & \!\ ! < \!\ ! & i(x_1 , x_2;y_m ) \end{ieeeeqnarraybox } \right\ } \end{ieeeeqnarraybox}\ ] ] for some product distribution @xmath54 . [ thrm : capreg ]      we now turn our attention to a random access system and apply theorem [ thrm : capreg ] to determine the capacity region of the system . each codeword symbol corresponds to a packet transmitted over the channel shown in figure [ fig : general_2sour2dest ] . we define the common input alphabet as @xmath55 , where @xmath56 , for @xmath9 . a channel input @xmath57 can be either a packet of length @xmath58 bits ( an information - bearing symbol ) or an idle symbol . the @xmath34 symbol is the idle symbol and we let pr@xmath59 according to the random access transmission probability . we assume a uniform distribution on the information - bearing codeword symbols , @xmath60 , @xmath61 , meaning that a packet is equally likely to be any sequence of @xmath58 bits . the channel output at receiver @xmath6 is given by @xmath62 where @xmath63 denotes the packet from source @xmath3 and @xmath64 . the @xmath65 symbol denotes a packet in error . the introduction of the idle symbol @xmath34 results in additional protocol or timing information being transmitted over the channel . the information content of this idle symbol is @xmath66 , where @xmath67 denotes the binary entropy function . the term @xmath68 appears in the proof provided below and represents the protocol information that is studied by gallager in @xcite . because we would like our capacity result to represent the rate of reliable communication of data packets , we will aim to exclude this timing information we do so by considering capacity in packets / slot in the limit as @xmath69 , meaning that the data packets grow large and the fraction of timing information transmitted approaches @xmath34 . the timing information is excluded in previous work on random access capacity . in @xcite , prior to the start of transmission , a `` protocol sequence '' indicating the occurrence of idle slots is generated at the source and communicated to the receiver , effectively eliminating timing information . in @xcite , the capacity for @xmath70 is presented . the capacity of the random access multicast system is given in the following corollary to theorem [ thrm : capreg ] . the capacity region of the random access system with two sources and two destinations is the closure of @xmath52 for which @xmath71 for some @xmath72 ^ 2 $ ] . [ cor : capacity ]    the result follows by applying the assumptions about the input distribution and channel reception probabilities to the expressions given in theorem [ thrm : capreg ] . we first solve for @xmath73 by conditioning on @xmath74 to obtain @xmath75 an expression for @xmath76 can be found from the following sequence of equalities . @xmath77 where @xmath78 holds since @xmath74 is independent of @xmath79 and since @xmath80 . for @xmath81 we have @xmath82 combining expressions ( [ eqn : hx1givenx2_1 ] ) and ( [ eqn : hx1givenx2_2 ] ) results in @xmath83 since one packet corresponds to @xmath58 bits , we divide by @xmath58 to obtain a result in units of packets per slot . we then let @xmath70 to obtain @xmath84 by following a similar approach , we can show that @xmath85 is given as follows . @xmath86 the bound on the sum rate can be found by breaking up @xmath87 into four terms . @xmath88 for @xmath9 , the terms @xmath89 can be expressed as @xmath90 the last two terms in ( [ eqn : ix1x2;y4terms ] ) can be found in the following manner . @xmath92 by substituting ( [ eqn : hxn ] ) , ( [ eqn : hx1giveny1x2 ] ) , and ( [ eqn : hx2giveny ] ) in ( [ eqn : ix1x2;y4terms ] ) , dividing by @xmath58 and taking @xmath69 , we obtain @xmath93 since @xmath94 , the bound on the sum rate is superfluous in terms of describing the capacity region . the result follows . in this section we treat the system shown in fig . [ fig : general_2sour2dest ] as a network of queues and state the stable throughput region of the system , which is a generalization of previous results on the stable throughput for a system with a single destination node . the model we consider is as follows . we no longer assume that the sources are always backlogged ; instead a random bernoulli process with rate @xmath95 packets / slot , @xmath9 models the arrival of packets at each source . packets that are not immediately transmitted are stored in an infinite - capacity buffer maintained at each source . transmissions occur according to the random access protocol with source @xmath3 transmitting with probability @xmath4 when it is backlogged . if a source is empty in a given slot , it does not access the channel . each source - destination pair is assumed to maintain an orthogonal feedback channel so that instantaneous and error - free acknowledgements can be sent from the destinations to the sources . we find the stable throughput region for two different transmission schemes : retransmissions and random linear coding . the queue at each source is described by its arrival process and departure process . as @xmath95 represents the arrival rate , we let @xmath96 denote the departure or service rate . in general , a queue is said to be stable if departures occur more frequently than arrivals , i.e. , @xmath97 . this statement is made precise by loynes result @xcite , which states that if the arrival and departure processes are non - negative , finite , and strictly stationary , then @xmath97 is a necessary and sufficient condition for stability . stability of the queue is equivalent to ergodicity of the markov chain representing the queue length . the stable throughput region for a given transmission policy is defined as the set of all @xmath98 for which there exists transmission probabilities @xmath99 such that both queues remain stable . the difficulty in finding the stable throughput region for our system ( and for any buffered random access system ) arises from the interaction of the queues . in particular , the service rate @xmath96 of source @xmath3 will vary according to whether the _ other _ source is empty or backlogged and can create interference on the channel . to overcome this difficulty , the technique provided in @xcite of introducing a dominant system can be used to decouple the sources . in a dominant system , one of the sources behaves as if it is always backlogged by transmitting `` dummy '' packets when it empties . the queue length in a dominant system stochastically dominates ( i.e. , is never smaller than ) the queue length in the system of interest , meaning that stability in a dominant system implies stability in the original system . since one source always behaves as if it is backlogged , the service rate in the dominant system can be easily found . let @xmath100 denote the service rate at source @xmath3 when the other source is backlogged and @xmath101 the service rate when the other source is empty . using the dominant systems approach , the stable throughput region for a system with two sources can be found exactly . this region is stated in the following theorem , which is a generalization of the result in @xcite . note that in the stable throughput region presented below , the service rates @xmath100 and @xmath101 are functions of @xmath4 , @xmath9 ( although not explicitly shown in these expressions ) . @xcite [ thrm:2x2stabreg ] for a network with two sources and two destinations , the stable throughput region is given by the closure of @xmath102 where @xmath103 and @xmath104[c]{r'l'l } \lambda_1 & \!\ ! < \!\ ! & \frac{\lambda_2}{\mu_{2b } } \mu_{1b } + \left ( 1 -\frac{\lambda_2}{\mu_{2b}}\right ) \mu_{1e } \\ \lambda_2 & \!\ ! < \!\ ! & \mu_{2b } \end{ieeeeqnarraybox } \right\}\ ] ] @xmath105[c]{r'l'l } \lambda_1 & \!\ ! < \!\ ! & \mu_{1b } \\ \lambda_2 & \!\ ! < \!\ ! & \frac{\lambda_1}{\mu_{1b } } \mu_{2b } + \left ( 1 - \frac{\lambda_1}{\mu_{1b } } \right ) \mu_{2e } \end{ieeeeqnarraybox } \right\}\ ] ] for some @xmath72 ^ 2 $ ] . in addition to the stable throughput region , we will be interested in the throughput region of the random access system shown in fig . [ fig : general_2sour2dest ] . the throughput region is the closure of the service rates @xmath100 for all @xmath4 , @xmath9 , where both sources are assumed to be backlogged . in finding the throughput region , there is no interaction between the sources , and the problem is simpler than finding the stable throughput problem . previous work on buffered random access systems has shown that in all cases in which the stable throughput region has been found , it is known to coincide with the throughput region , suggesting that the empty state of the buffer is insignificant in determining stability . the relation between stable throughput and throughput is explored in @xcite . additionally , in @xcite , it is proved that for a random access system with two sources and two destinations , the stable throughput region coincides with the throughput region . this result is restated below . @xcite the stable throughput region of the random access system with two sources and two destinations is equivalent to the throughput region , which is given by the closure of @xmath98 for which @xmath106 for some @xmath72 ^ 2 $ ] . [ theorem : throughput ]    we derive the backlogged and empty service rates @xmath100 and @xmath101 for two different transmission schemes . together with theorems [ thrm:2x2stabreg ] and [ theorem : throughput ] , this provides us a complete characterization of the stable throughput region . in this section we describe the stable throughput region under assuming that a retransmission protocol is used to ensure reliable communication . in the retransmission scheme , as long as source @xmath3 has not received feedback acknowledgements from both destinations @xmath10 , it will continue to transmit the packet over the channel with probability @xmath4 in each slot . as soon as the source has received acknowledgements from both destinations , it will remove the packet from its queue and begin transmitting the next packet waiting in its buffer , if any . let random variable @xmath107 denote the service time for source @xmath3 , given by the total number of slots that transpire before the packet from source @xmath3 is successfully received at both destinations . ( note that the service time includes slots during which the source does not transmit , which happens with probability @xmath108 ) . since each completed service in the retransmission scheme results in 1 packet being removed from the queue , the average service rate is given by @xmath109 $ ] . we first find the backlogged service rates @xmath100 . let @xmath110 denote the number of slots needed for successful reception of a packet from source @xmath3 at destination @xmath6 , @xmath10 . the @xmath110 are geometrically distributed according to the transmission probabilities @xmath4 and reception probabilities @xmath111 , @xmath112 . we introduce the following notation . let @xmath113 denote the probability of successful reception of the packet from source @xmath3 at destination 1 given that source @xmath3 transmits and that both sources are backlogged . similarly , @xmath114 denotes the probability of successful reception at destination 2 given that both sources are backlogged and that source @xmath3 transmits . for instance , @xmath115 and @xmath116 are given by @xmath117 where @xmath118 . when source 2 is backlogged , @xmath119 is geometrically distributed with parameter @xmath120 and @xmath121 is geometrically distributed with parameter @xmath122 . the total service time for source 1 when source 2 is backlogged will be given by the maximum of the service times to each destination , @xmath123 similarly , when source 1 is backlogged , the service time for source 2 is given by @xmath124 where @xmath125 the expected maximum value @xmath126 $ ] can be readily found and the backlogged service rates are given by @xmath127 where @xmath128 denotes the probability that a packet sent from @xmath3 is received at both destinations given that source @xmath3 transmits , e.g. , @xmath129 . the empty service rates @xmath101 can be found directly from @xmath100 as @xmath130 the backlogged and empty service rates for random access multicast with retransmissions have also been found in @xcite . in that work , a different approach is used in which a markov chain is used to model which destinations have received the packet currently under transmission . the result is identical to the one presented above . we now compare the stable throughput region for the retransmissions scheme to the shannon capacity region . we consider the backlogged service rate @xmath100 , since , by theorem [ theorem : throughput ] , this is the term that bounds the stable throughput for source @xmath3 . the expected service time for source 1 when source 2 is backlogged is bounded as @xmath131 = e[\max_m t_1^{(m ) } ] & \stackrel{(a ) } \geq & \max_m e[t_1^{(m ) } ] \\   & \stackrel{(b ) } = & \max_m \frac{1}{p_1 ( 1-p_2 ) q_{1|1}^{(m ) } + p_1 p_2 q_{1|1,2}^{(m ) } } \\   & = & \frac{1}{\min_m p_1 ( 1-p_2 ) q_{1|1}^{(m ) } + p_1 p_2 q_{1|1,2}^{(m)}}\end{aligned}\ ] ] where @xmath78 follows from jensen s inequality and @xmath132 follows from the expected value of a geometrically distributed random variable . then the backlogged service rate @xmath133 is bounded as @xmath134 } \leq \min_m p_1 ( 1-p_2 ) q_{1|1}^{(m ) } + p_1 p_2 q_{1|1,2}^{(m ) } \label{eqn : boundretransservrate}\ ] ] and @xmath135 can be bounded similarly . note that the right - hand side of ( [ eqn : boundretransservrate ] ) is equal to the bound on the shannon achievable rate @xmath136 given in corollary [ cor : capacity ] . thus we should expect that the shannon capacity region outer bounds the stable throughput region for the retransmission scheme . in this section we present two different approaches to analyzing the stable throughput region for a transmission scheme in which groups of @xmath137 packets at the front of the queue are randomly encoded and transmitted over the channel . by encoded , we mean that a random linear combination of the @xmath137 packets is formed , and we refer to this random linear combination as a coded packet . as soon as a destination has received enough coded packets and is able to decode the original @xmath137 packets , it does so and sends an acknowledgement to the source over its feedback channel . once the source receives acknowledgements from both destinations , it removes the @xmath137 packets it has been encoding and transmitting from its queue and begins encoding and transmission of the next @xmath137 packets waiting in its buffer . the stable throughput region for a similar system with @xmath138 is found in @xcite . for a given source , let @xmath139 denote the @xmath137 ( binary ) packets at the front of the queue . random linear coding is performed in the following manner . a coded packet is randomly generated as @xmath140 where the coefficients @xmath141 are generated according to @xmath142 , @xmath143 , and @xmath144 denotes modulo-2 addition . a coded packet formed in this way is the same length as one of the original packets @xmath145 and can be transmitted over the channel within the same time period of a slot . for each coded packet sent , the coefficients @xmath141 used in generating the packet will be appended to the header of the packet . in each slot , the source generates a coded packet according to ( [ eqn : rlccodedpacket ] ) and sends it over the channel . regardless of whether a previously - generated coded packet has been received , the source generates a new coded packet in each slot and transmits it with probability @xmath4 . we first analyze the random linear coding scheme by examining the expected service time in a manner similar to the approach used for the retransmission scheme in section [ section : stabilityretrans ] . let @xmath146 denote the service time for source @xmath3 , which is the number of slots that elapse from the transmission of the first coded packet until the source has received acknowledgements from both destinations . since each completed service in the random linear coding scheme results in @xmath137 packets being removed from the queue , the average service rate is given by @xmath147 $ ] . the service time will be a random variable dependent upon the random access transmission probabilities @xmath4 , the reception probabilities @xmath111 and @xmath112 , and the number of coded packets needed to decode . let @xmath148 denote the number of coded packets received from source @xmath3 at destination @xmath6 before destination @xmath6 can decode the original @xmath137 packets . the @xmath148 will be identically distributed over @xmath3 and @xmath6 since all coded packets are generated in the same way according to ( [ eqn : rlccodedpacket ] ) . additionally , @xmath148 will be independent over @xmath3 since the two sources generate their coded packets independently . however , @xmath148 will be correlated over @xmath6 , since a given source @xmath3 will generate and transmit the same coded packets to both destinations @xmath10 .    for a fixed value of @xmath137 , let @xmath149 denote the common cumulative distribution function ( cdf ) of @xmath148 , or the probability that the number of coded packets needed for decoding is less than or equal to @xmath150 . with each coded packet it receives , the destination collects a binary column of length @xmath137 in a matrix , where the column consists of the coefficients @xmath141 , @xmath143 . then @xmath149 is the probability that decoding can be performed ( by solving a system of linear equations , or equivalently , by gaussian elimination ) if the matrix has at most @xmath150 columns . thus @xmath151 note that for @xmath152 the matrix can not possibly have rank @xmath137 and @xmath153 . for @xmath154 , we can write an expression for @xmath149 following the procedure in @xcite by first counting up the number of @xmath155 non - singular matrices , which is given by @xmath156 in the product above , each term accounts for a row of the @xmath157 binary matrix and reflects that the row is neither zero , nor equal to any of the previous rows , nor equal to any linear combination of previous rows . since the total number of @xmath155 binary matrices is @xmath158 , we obtain @xmath159 the probability mass function ( pmf ) of @xmath148 , or the probability that decoding can be performed when the destination has received exactly @xmath150 columns and no fewer , is given by @xmath160 from ( [ eqn : cdfn ] ) and ( [ eqn : pmfnascdfn ] ) the expected value of @xmath148 can be computed , where @xmath161 \geq k$ ] . the ratio @xmath162}{k } & = & \prod_{i=0}^{k-1 } ( 1 - 2^{-k+i } ) + \frac{1}{k } \sum_{j = k+1}^{\infty } j \left ( \prod_{i=0}^{k-1 } ( 1 - 2^{-j+i } ) - \prod_{i=0}^{k-1 } ( 1 - 2^{-j+1+i } ) \right ) \\   & \longrightarrow & 1 \quad \mbox {   as } k \rightarrow \infty\end{aligned}\ ] ] for all @xmath163 .    with the distribution of @xmath148 characterized , we can now describe the service time from source @xmath3 to destination @xmath6 , which we denote @xmath164 . the number of slots needed for the successful reception of each coded packet will be geometrically distributed and in total @xmath148 coded packets must be received . then @xmath164 can be modeled as the sum of @xmath148 independent geometrically distributed random variables . @xmath165 in the above expression , @xmath166 , @xmath167 , will be geometrically distributed with a parameter that depends on the reception probabilities and on the assumption of whether the other source is backlogged . for instance , when source 2 is backlogged @xmath168 and when source 2 is empty , @xmath169 the total service time is given as @xmath170 as in the case of random access with retransmissions , we argue that the stable throughput region for random access with random linear coding will be outer bounded by the shannon capacity region . in the case that source 2 is backlogged , the expected service time for source 1 is now bounded as @xmath171 = e[\max_m \widetilde{t}_1^{(m ) } ] & \stackrel{(a ) } \geq & \max_m e[\widetilde{t}_1^{(m ) } ] \\   & \stackrel{(b ) } = & \max_m   \frac{e[n_{1}^{(m)}]}{p_1 ( 1-p_2 ) q_{1|1}^{(m ) } + p_1 p_2 q_{1|1,2}^{(m ) } } \\   & \stackrel{(c)}= & \frac{e[n_{1}^{(m)}]}{\min_m p_1 ( 1-p_2 ) q_{1|1}^{(m ) } + p_1 p_2 q_{1|1,2}^{(m)}}\end{aligned}\ ] ] where @xmath78 again follows from jensen s inequality , @xmath132 holds since @xmath172 are independent , identically distributed , and @xmath173 holds since @xmath174 is identically distributed over @xmath6 , meaning that @xmath175=e[n_{1}^{(2)}]$ ] . the backlogged service rate @xmath176 is bounded as @xmath177 } & \leq & \frac{k}{e[n_{1}^{(m ) } ] } \min_m p_1 ( 1-p_2)q_{1|1}^{(m ) } + p_1p_2q_{1|1,2}^{(m ) } \\ & \leq & \min_m p_1 ( 1-p_2)q_{1|1}^{(m ) } + p_1p_2q_{1|1,2}^{(m)}.\end{aligned}\ ] ] then the shannon capacity region outer bounds the stable throughput region for random access with random linear coding . unfortunately a difficulty arises in finding the service rates @xmath100 and @xmath101 in closed form from @xmath178 $ ] . this difficulty arises for a number of reasons : @xmath179 and @xmath180 are not independent , and @xmath164 is distributed according to a composite distribution function , for which the pdf is not easily expressed in closed form . in fact , even if these two difficulties were to be removed , @xmath181 $ ] can not be easily handled . for instance , let us assume that @xmath179 and @xmath180 are independent and that @xmath182 are deterministic ( which means that the pdf is no longer composite ) . in that case , @xmath164 is the sum of @xmath183 iid geometric random variables , meaning that @xmath164 follows a negative binomial distribution . let us further make the assumption that @xmath184 and @xmath185 , which means that @xmath164 are identically distributed over @xmath6 . in this very simplified case , @xmath178 $ ] is the expected maximum of two iid negative binomial random variables . the computation of this expected value is treated in @xcite , and the result involves a periodic function which is approximated by a fourier series . thus , even in this very simplified case , we can at best approximate @xmath186 $ ] , and this approximation must be computed numerically .      as an alternative to the analysis presented above , we now develop a markov chain model which allows us to find the queueing service rates . for a given source node , we set up a vector markov chain with state @xmath187 corresponding to the number of linearly independent coded packets that have been received from the source node . in this model , @xmath188 represents the number of linearly independent coded packets that have been received at destination 1 , and @xmath150 represents the number of linearly independent packets that have been received at destination 2 . since the coded packets are generated by the same source , some of the coded packets received at destination 1 may also have been received at destination 2 , and @xmath189 represents the number of such packets , where @xmath190 . the variable @xmath189 allows us to track the correlation between @xmath191 and @xmath192 , which was a difficulty in our previous approach described above . the markov chain evolves in discrete time over the time slots in our system model . the state space of the markov chain is the three - dimensional discrete set of points @xmath193 ^ 3 $ ] . there are @xmath194 absorbing states given by @xmath195 , @xmath196 , which represent the reception of @xmath137 linearly independent coded packets at both destinations , for which the service of @xmath137 packets at the source has been completed . transitions in the markov chain can only occur `` upward '' , corresponding to the reception of a new linearly independent packet , and a transition results in an increase of the indices @xmath197 by at most 1 , meaning that at most 1 new linearly independent packet can be received in a slot . we use the notation @xmath198 to denote the transition from state @xmath199 to state @xmath200 . the markov chain is irreducible and aperiodic , and because it has a finite state space , a stationary distribution exists . let @xmath201 denote the steady - state probability of @xmath187 . the steady - state probabilities are found by solving the set of equations @xmath202 and @xmath203 the service rate @xmath204 is equal to @xmath137 times the probability of transitioning into an absorbing state @xmath195 , @xmath205 . there are only a few ways to transition into an absorbing state ; let @xmath206 denote the set of states which have a one - step transition into the absorbing state @xmath195 . for @xmath207 $ ] we have @xmath208 and for @xmath209 , @xmath210 note that we define @xmath211 in this way since the states @xmath212 and @xmath213 violate @xmath190 . the service rate for source @xmath3 is given by @xmath214 the transition probabilities @xmath215 for source @xmath3 can be written assuming that the other source is either backlogged or empty , leading to the service rates @xmath216 and @xmath217 . as an example , consider the transition @xmath218 in the markov chain for source 1 when source two is backlogged . assume first that source two does not transmit , which happens with probability @xmath219 . then there are two ways for the transition @xmath220 to occur . first , destination 2 could receive no packet , which happens with probability @xmath221 , while destination 1 receives a coded packet which is neither an all - zero packet nor equal to any linear combination of the @xmath188 packets it has already received , which happens with probability @xmath222 . alternatively , both destinations could receive a coded packet , but that packet is either the all zero packet or some linear combination of the packets that have been received by destination 2 and _ not _ by destination 1 . this happens with probability @xmath223 . the same two alternatives are possible in the case that source 2 does transmit , which happens with probability @xmath224 , except that the reception probabilities are now given by @xmath225 . then the transition @xmath218 for source 1 when source 2 is backlogged occurs with probability @xmath226.\end{gathered}\ ] ] the same transition probability can be used when source 2 is empty by setting @xmath227 . similar arguments can be used to find all transition probabilities for our markov chain model ; we have stated those probabilities in appendix [ app : rlcmctransprob ] . ultimately , we would like to find closed - form expressions for the service rates @xmath216 and @xmath217 , but due to the size of the state - space , this is a difficult task . instead we have computed some numerical examples based on the markov chain model presented above , and those are presented next . , @xmath228 , and @xmath229 . the stable throughput region for random linear coding is abbreviated rlc.,scaledwidth=70.0% ]    we have computed a number of numerical examples of the shannon capacity region and the stable throughput regions for retransmissions and random linear coding . the results for random linear coding have been computed with the service rates given by equation ( [ eqn : murlcmc ] ) . [ fig : resultsstrongmpr ] shows results for a `` good '' channel with relatively large reception probabilities while fig . [ fig : resultsweakmpr ] shows results for a `` poor '' channel with smaller reception probabilities . in both figures , we have plotted the stable throughput for random linear coding ( abbreviated `` rlc '' ) with various values of @xmath137 . the results show that the shannon capacity region is strictly larger than the stable throughput regions for both the retransmissions and random linear coding schemes . additionally , the stable throughput region for random linear coding grows with @xmath137 and appears to approach the capacity as @xmath230 . the random linear coding scheme does not necessarily outperform the retransmission scheme . for small values of @xmath137 , the coding scheme is inefficient in the sense that the ratio @xmath231 $ ] is small . this inefficiency is largely due to the fact that an all - zero coded packet can be generated and transmitted ; this possibility is not precluded in ( [ eqn : rlccodedpacket ] ) and occurs more often for small values of @xmath137 . the inefficiency of the coding scheme means that the retransmission of @xmath137 packets requires a service time that is less than @xmath232 $ ] for small values of @xmath137 . this effect seems to become more pronounced as the channel improves , since for a `` good '' channel , packets are more often received correctly and do not need to be retransmitted .    , @xmath228 , and @xmath233 . the stable throughput region for random linear coding is abbreviated rlc.,scaledwidth=70.0% ] one conclusion to draw from our work is that for sufficiently large blocklengths , given by @xmath137 in our model , coding over packets in a queue yields a higher stable multicast throughput than simply retransmitting lost packets . in light of the recent developments on network coding and fountain codes , this result is not surprising . however , we have also shown that if the blocklength is too small and the code is not designed appropriately , then a retransmission scheme can provide a higher stable throughput than coding . furthermore , we have combined random access with random linear coding to yield an efficient multicast scheme that can operate in a completely distributed manner . we have shown that the merging of random access with random linear coding results in good performance in the sense that the stable throughput approaches the shannon capacity . in the process , we have presented a model that represents random coding of packets in a queue . another significant outcome of our work is that we have provided an example of a transmission policy for which the stable throughput region _ does not _ coincide with the shannon capacity region of a random access system . this outcome contradicts a widely - held ( yet unproved ) belief that the stability and capacity regions coincide for random access . this result sheds further light on the relation between the stable throughput and the shannon capacity as representations for the rate of reliable communication . let @xmath234 denote the error probability for the @xmath22 message from the sources at receiver @xmath6 . @xmath235 the following lemma provides a condition equivalent to @xmath49 and is used in the proof of theorem [ thrm : capreg ] .    the average error @xmath236 if and only if @xmath237 . [ lemma : errorcond ]    the average error @xmath44 can be upper bounded by the union bound as follows : @xmath238 . a similar lower bound also holds , namely @xmath239 . thus @xmath240 and the result follows . achievability for our system is shown by first establishing achievability for the mac @xmath241 . this is shown in @xcite and @xcite ; the approach presented in @xcite is summarized here . each codeword symbol in the codebook for source @xmath3 is generated according to the distribution @xmath242 , independently over codeword symbols and independently over messages . the following two properties are assumed .    1 . the codewords @xmath243 and @xmath244 are reserved for use as preambles . a preamble is sent after every sequence of @xmath245 messages and @xmath243 and @xmath244 are used as preambles in an alternating fashion . in @xcite it is shown that by using the preamble , the receiver can synchronize on codeword boundaries with arbitrarily small probability of synchronization error . 2 .   in a sequence of @xmath37 messages ( including a preamble ) , no messages are repeated . as a result , any two disjoint subsets of @xmath36 codeword symbols ( corresponding to @xmath37 messages ) are independent . for @xmath246 the resulting loss in rate is negligible .    by observing the channel outputs , the decoder @xmath247 can detect the preambles @xmath248 and @xmath249 to determine that the output symbols in between correspond to inputs @xmath250 . let @xmath251 denote the sequence of @xmath36 symbols corresponding to @xmath250 augmented by portions of the preambles @xmath248 and @xmath252 . at the channel output , @xmath251 will overlap with a sequence @xmath253 consisting of @xmath36 symbols input by source 2 , including @xmath16 preamble symbols . let @xmath254 denote the output sequences corresponding to @xmath251 and @xmath253 at destination @xmath6 . the decoder @xmath247 outputs the unique sequence of messages @xmath255 that lies in the set of typical @xmath256 sequences . with this approach it is shown in @xcite that @xmath257 for all @xmath50 . a similar technique can be used by decoder @xmath258 to show that @xmath259 . then by the union bound , @xmath260 for all @xmath50 . finally , if the rate pair @xmath52 lies in the intersection of the achievable rates for macs @xmath261 and @xmath262 , then @xmath263 and thus @xmath236 for all @xmath50 by lemma [ lemma : errorcond ] .    the converse for the mac @xmath241 is shown in @xcite and @xcite by using fano s inequality , the data processing inequality , and the concavity of mutual information . then @xmath264 implies that the rate pair @xmath52 must lie within the intersection of the capacity regions of @xmath261 and @xmath262 . in the markov chain analysis of section [ subsection : rlcmarkovchain ] , the state @xmath187 represents @xmath188 linearly independent coded packets received at destination 1 , @xmath150 linearly independent coded packets received at destination 2 , and @xmath189 coded packets which have been received at both destinations , @xmath265 . when source 2 is backlogged , the non - zero transition probabilities for source 1 are given as follows for @xmath266 . rl ( i , j , k ) ( i , j , k ) : & _ 1 + p_1 + ( i , j , k ) ( i+1,j , k ) : & p_1 + ( i , j , k ) ( i , j+1,k ) : & p_1 + ( i , j , k ) ( i+1,j+1,k+1 ) : & p_1 +    rl ( i , k , k ) ( i , k , k ) : & _ 1 + p_1 + ( i , k , k ) ( i+1,k , k ) : & p_1 + ( i , k , k ) ( i+1,k , k+1 ) : & p_1 +    rl ( k , j , k ) ( k , j , k ) : & _ 1 + p_1 + ( k , j , k ) ( k , j+1,k ) : & p_1 + ( k , j , k ) ( k , j+1,k+1 ) : & p_1 + the authors wish to thank gerhard kramer for helpful comments which greatly improved the manuscript . p.  j. grabner and h.  prodinger , `` maximum statistics of @xmath3 random variables distributed by the negative binomial distribution , '' _ combinatorics , probability and computing _ , vol . 179183 , 1997 .
we study and compare the shannon capacity region and the stable throughput region for a random access system in which source nodes multicast their messages to multiple destination nodes . under an erasure channel model which accounts for interference and 
 allows for multipacket reception , we first characterize the shannon capacity region . 
 we then consider a queueing - theoretic formulation and characterize the stable throughput region for two different transmission policies : a retransmission policy and random linear coding . 
 our results indicate that for large blocklengths , the random linear coding policy provides a higher stable throughput than the retransmission policy . 
 furthermore , our results provide an example of a transmission policy for which the shannon capacity region strictly outer bounds the stable throughput region , which contradicts an unproven conjecture that the shannon capacity and stable throughput coincide for random access systems . 
 wireless multicast , random access , aloha , queueing , stability , throughput , capacity , retransmissions , random linear coding