{'fraction_non_alphanumeric': 0.04346781940441883, 'fraction_numerical': 0.007660902977905859, 'mean_word_length': 4.001921921921922, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Frame Asynchronous Coded Slotted ALOHA: Asymptotic, Finite Length, and Delay Analysis

We consider a frame asynchronous coded slotted ALOHA (FA-CSA) system for uncoordinated multiple access, where users join the system on a slot-by-slot basis according to a Poisson random process and, in contrast to standard frame synchronous CSA (FS-CSA), users are not frame-synchronized. We analyze the performance of FA-CSA in terms of packet loss rate and delay. In particular, we derive the (approximate) density evolution that characterizes the asymptotic performance of FA-CSA when the frame length goes to infinity. We show that, if the receiver can monitor the system before anyone starts transmitting, a boundary effect similar to that of spatially-coupled codes occurs, which greatly improves the iterative decoding threshold. Furthermore, we derive tight approximations of the error floor for the finite frame length regime, based on the probability of occurrence of the most frequent stopping sets. We show that, in general, FA-CSA provides better performance in both the EF and waterfall regions as compared to FS-CSA. Moreover, FA-CSA exhibits better delay properties than FS-CSA.


I. INTRODUCTION
U NCOORDINATED multiple access is necessary in any communications system where coordinated resource allocation is not possible or too costly. Classical uncoordinated techniques include the ALOHA systems introduced in the 1970s [1], [2] and carrier sense based techniques [3], such as carrier sense multiple access with collision avoidance. To provide reliable communication, these techniques typically require a retransmission policy, which introduces the need for a separate feedback channel and incurs in a possibly large delay.
Recently, a considerable interest for finding novel solutions to provide reliable, low latency communication in dynamical systems has emerged, driven by the stringent requirements of the upcoming 5G communication systems [4]. One promising uncoordinated multiple access technique is coded slotted ALOHA (CSA) [5], [6]. CSA builds on the classical slotted ALOHA technique and borrows ideas from error correcting codes to provide highly reliable uncoordinated multiple access.
In CSA, transmission is organized into frames, each consisting of the same number of slots. Two key ingredients of CSA is to let users replicate each packet a number of times within a frame and to perform iterative decoding using successive interference cancellation (SIC) [5]. Furthermore, in standard CSA, referred to as frame synchronous CSA (FS-CSA) in the sequel, all users are assumed to be frame-synchronized. A major contribution made in [6] was realizing that there exists a connection between CSA and codes on graphs. Indeed, a CSA system can be described by a bipartite graph and SIC can be performed over the graph similarly to decoding of graph-based codes. Therefore, it is not surprising that the performance of CSA resembles that of graph-based codes, i.e., the packet loss rate (PLR) curve is characterized by a waterfall (WF) region for medium-to-high system loads and it shows an error floor (EF) for low system loads. Furthermore, in the asymptotic regime of infinite frame length, CSA exhibits a threshold behavior, which can be characterized using density evolution (DE). The DE for FS-CSA was derived in [6].
To improve the delay performance of FS-CSA, a frame asynchronous CSA (FA-CSA) system was proposed in [7]. In contrast to FS-CSA, in FA-CSA users are not framesynchronized. Instead, a user that joins the system selects slots for its packet replicas from a number of subsequent slots, which form its local frame. The duration of the local frame (in number of slots) for each user is the same. It was shown in [7] that, in addition to improve the average delay, FA-CSA outperforms FS-CSA in terms of throughput.
In this paper, we provide a thorough analysis of the PLR of FA-CSA in the asymptotic and finite frame length regime. More specifically, we derive the (approximate) DE that governs the asymptotic performance of FA-CSA in the limit of very large frame lengths. Interestingly, if the receiver can monitor the system before transmitting, a boundary effect similar to that of spatially-coupled codes naturally arises. This greatly improves the iterative decoding threshold as compared to that of FS-CSA. Similar improved thresholds were achieved in [8], where the concept of spatial coupling was applied to CSA. However, while the spatially coupled structure is enforced by design in [8], in FA-CSA it is inherent to the system. We also derive analytical approximations of the PLR in the finite frame length regime in order to predict the EF of FA-CSA. The analysis is based on the framework introduced in [9] and [10], where the probability of occurrence of minimal stopping sets is used to approximate the PLR of FS-CSA. The EF of FA FS-CSA was also analyzed in [11], [12]. However, the analysis is restricted to regular distributions and considers a single, trivial stopping set. We show that in the finite frame length regime FA-CSA yields superior performance than that of FS-CSA in both the WF and EF regions. Furthermore, by means of simulations, we analyze the delay performance of FA-CSA and show that FA-CSA yields lower average delay than FS-CSA, albeit at the cost of a higher maximum delay. We then compare FA-CSA and FS-CSA with a constraint on the maximum delay and receiver memory size, and show that, FA-CSA achieves better PLR than FS-CSA also in this case. Finally, we compare FA-CSA and spatially-coupled CSA (SC-CSA) in the finite frame length regime. It is shown that FA-CSA performs better than SC-CSA, both in terms of PLR and delay.
II. SYSTEM MODEL We consider a CSA system with multiple users transmitting to a common receiver, where time is divided into slots, each of duration τ , and where users are slot-synchronized. A user that joins the system generates a message and selects a repetition factor l randomly according to a predefined degree distribution [6]. The message is then mapped into a physical layer packet of duration τ (including guard intervals), such that one packet can be sent within one slot. The user transmits l copies (called replicas) of the packet in randomly selected slots. A user that repeats its packet l times is called a degree-l user and similarly a slot containing r replicas from different users is called a degree-r slot. It is assumed that a packet can always be decoded if at least one of its replicas is in a degree-1 slot. Furthermore, to facilitate decoding, each replica of a packet contains pointers to all other replicas of that packet. Throughout the paper we assume that perfect interference cancellation (IC) can be performed to remove the interference of a user's replicas once its packet has been decoded. This assumption makes the analysis of the system more feasible. In [5], [6] actual (low complexity) IC was implemented with little performance degradation as compared to perfect IC.
We assume that users join the system on a slot basis according to a Poisson process and let K denote the number of users that join in a slot. Then K is a Poisson distributed random variable (RV) with mean g, K ∼ Po(g), where g is the average system load in users per slot. The probability that k users join the system in a given slot is thus, This is a common user model for multiple access techniques, used, e.g., in the original ALOHA systems [1], [2]. We define the two most important performance measures for CSA. Definition 1. The PLR, denoted byp, is the average probability that the packet of an arbitrary user is never resolved. Definition 2. The delay of a resolved user's packet is the number of slots between the slot a user joins the system and the slot following the decoding of its packet.

A. Frame Synchronous Coded Slotted ALOHA
In FS-CSA, communication takes place during global frames consisting of n slots each. A degree-l user that joins the system waits until the next frame and transmits its l replicas in randomly chosen slots of that frame. We then say that the user is active during the whole duration of the frame. We denote by M ∼ Po(ng) the RV representing the number of active users per frame. Note that the active users in a frame are all the users that joined the system during the previous frame.
Decoding of FS-CSA is performed on a slot-by-slot basis. Assume the decoding of slot i. First, the interference caused by packets for which replicas in previous slots have already been decoded is canceled from the slot. The receiver then checks if slot i is a degree-1 slot and, if not, the decoding of slot i is stopped. Otherwise, the packet in slot i is decoded and the interference from all its replicas canceled from the corresponding past slots. The receiver then proceeds to iteratively find any degree-1 slots in its memory, decode the packets in these slots, and cancel the interference of all replicas of the decoded packets. This process continues until no new degree-1 slots are found or a maximum number of iterations is reached.

B. Frame Asynchronous Coded Slotted ALOHA
In FA-CSA, when a degree-l user joins the system it transmits a first replica in the following slot. The remaining l − 1 replicas are distributed uniformly within the n − 1 subsequent slots. Similarly to FS-CSA, n is the frame length of FA-CSA. However, contrary to FS-CSA, slots are not arranged in global frames. We say that a user is active during the n slots following the slot where it joins the system and, accordingly, we call the n slots where a user is active its local frame. Because a user always transmits in the first slot of its local frame, we call this system FA-CSA with first slot fixed (FA-CSA-F).
Decoding of FA-CSA is performed in a similar way as for FS-CSA, with the only difference that the receiver needs to consider not only the slots of a current frame, but all slots of the entire history of the system. In practice, the receiver cannot consider infinitely many slots and has a finite memory. We denote by n RX the size of the receiver memory in number of slots. A finite n RX creates the notion of a sliding-window decoder. It was shown in [7] that increasing n RX beyond 5n does not improve performance in general.
We let denote the number of active users in the ith slot, which is Poisson distributed with mean µ i . The active users in slot i are all users that joined the system in the slots [i − n, i − 1]. We consider two different models for the initialization of the system, i.e., for 1 ≤ i ≤ n. The first model assumes that there are no active users at i = 0. In this case and we say that a boundary effect is present for this model. Effectively, this means that the n − 1 first slots of the system have lower average degree than the rest. The second model assumes that there are already M ∼ Po(ng) active users at i = 0. Thus, For this model, all considered slots have the same average degree.
The system with boundary effect corresponds to a system where the receiver is present at the very start of the communication or, potentially, a system with periods of low load. A  practical example is road side infrastructures in a vehicular network as the intended receivers. On the other hand, the model with no boundary effect is useful for systems where the receiver joins an already ongoing communication, e.g., a vehicle in a local vehicular network as the intended receiver. A vehicle will join and leave local networks with ongoing communication as it is moving. In addition to the initialization models described above, we introduce a second model for the selection of slots for transmission aside from that of FA-CSA-F, where a degreel user selects all l slots for transmission randomly from the local frame. We call this system FA-CSA with uniform slot selection (FA-CSA-U). FA-CSA-U is more similar to FS-CSA and provides a simplified analysis in some cases. However, we remark that FA-CSA-F is more practical and, as it it is shown later, performs better in general. Therefore, the main focus of this paper is on FA-CSA-F.

FA-CSA
In all, we consider four models for FA-CSA, i.e., FA-CSA with first slot fixed and boundary effect (FA-CSA-FB), FA-CSA with first slot fixed and no boundary effect (FA-CSA-FNB), FA-CSA with uniform slot selection and boundary effect (FA-CSA-UB), and FA-CSA with uniform slot selection and no boundary effect (FA-CSA-UNB). The terminology "boundary effect" will become clearer in Sections III and IV.

C. Graph Representation
An instance of a CSA system can be completely represented by a bipartite graph G = {V, C, E}, where V is the set of variable nodes (VNs), C is the set of check nodes (CNs), and E is the set of edges connecting the VNs and CNs. VNs represent users and CNs represent slots. There is an edge e i→j ∈ E from VN i to CN j if user i transmits a replica in slot j. Decoding of CSA can be viewed as message passing on the underlying graph [6]. The degree of a node is equal to the number of edges incident to the node. Example 1. An example of FS-CSA and FA-CSA-FB is depicted in Fig. 1, with n = 6, g = 0.5, and where users select degree 2 or 3 with equal probability. Gray areas show the frames of FS-CSA and local frames for each user in FA-CSA-FB. Slots filled with green represent packets of degree-2 users and slots filled with blue represents packets of degree-3 users. The delay of each user is indicated by a number in the slot in which it is decoded. Furthermore, the four striped green slots in the second frame of the FS-CSA example collide in such a way that the packets in these slots can not be decoded. Such collision patterns are called stopping sets.
In Fig. 2, the graph representation for the two scenarios (FS and FA) in Fig. 1 is depicted.

III. DEGREE DISTRIBUTIONS
In this section, we derive the VN-and CN-degree distributions for FA-CSA. We define the node-perspective VN-and CN-degree distribution as respectively, where Λ l is the probability that an arbitrary VN has degree l and P r is the probability that a CN has degree r. Λ(x) is under the control of the system designer and is subject to optimization. We introduce also the edge-perspective VNand CN-degree distributions where λ l denotes the probability that an edge is connected to a degree-l VN and ρ r denotes the probability that an edge is connected to a degree-r CN. The probabilities λ l and ρ r are given by i.e., λ(x) = Λ (x)/Λ (1) and ρ(x) = P (x)/ P (1), where f denotes the derivative of the function f .

A. Frame Asynchronous CSA with First Slot Fixed
For FA-CSA with boundary effect, the first n CNs all have distinct degree distributions. This gives rise to different classes of CNs and VNs. We call a CN at position i (slot i) a class-i CN. Similarly, a VN at position i is a class-i VN. Additionally, in FA-CSA-F a degree-l class-i VN always has one connection to a class-i CN, i.e., a fixed edge, and it has l − 1 connections to randomly selected CNs of classes The node connectivity for class-i VNs and CNs of FA-CSA-F is depicted in Fig. 3. Accordingly, we define the nodeperspective VN-degree distributions for FA-CSA-F where Λ i→i (x) represents the fixed connection, Λ i→Ji l = Λ l+1 is the probability that a class-i VN has l connections to CNs of classes in J i , and in (a) we made the change of variables l → l−1. The corresponding edge-perspective degree distributions are, . On the other hand, a class-i CN is connected to r 1 class-i VNs and to r 2 VNs of classes in the range Correspondingly, we define the degree fdistributions is the probability that a class-i CN has r 1 edges incident to class-i VNs, and P i→Ki r2 is the probability that a class-i CN has r 2 connections to VNs of classes in K i . The corresponding edge-perspective degree distributions are and Proposition 1. The class-i CN degree distributions for FA-CSA-F are given by and Proof: Denote by R 1 the RV representing the number of edges connecting a class-i CN to class-i VNs. Clearly, R 1 ∼ Po(g), because each class-i VN is connected through a single edge to the class-i CN. Therefore, Now P i→i (x) is given by where in (a) we used that ∞ n=0 x n n! = exp(x). Furthermore, We now denote by R 2,i the number of edges connecting a class-i CN to VNs of classes in the range K i , as given in (11). The number of VNs in K i is a Poisson RV, denoted by K i , with mean δ i given in (17). Each VN in K i connects to the class-i CN with probability Applying the law of total probability this gives, where in (a) we used k = k − r 2 and k ← k and in (b) we used that ∞ n=0 x n n! = exp(x). Following similar steps as in (19) and (20) gives where p is given in (21).

B. Frame Asynchronous CSA with Uniform Slot Selection
For FA-CSA-U, we need to consider only one degree distribution per CN class, as defined in (5). We denote by P i (x) and ρ i (x) the node-perspective and edge-perspective class-i CN degree distributions, respectively. Proposition 2. The class-i CN degree distribution for FA-CSA-U is given by where for FA-CSA-UB µ i is given by (3) and for FA-CSA-UNB µ i is given by (4).
Proof: A class-i CN can be connected with any of the M i VNs at position i. The probability that each of the M i VNs connects to the class-i CN is Λ (1)/n. This setup is similar to the setup for the derivation of P i→Ki (x) in Lemma 1. Taking similar steps, it directly follows that The CN degree distribution for FS-CSA, derived in [6], holds also when a Poisson user model is used, although the assumption that n → ∞ is not necessary. In fact, the CN degree distributions for FA-CSA-UNB and FS-CSA are the same, which is expected since FA-CSA-U is similar to FS-CSA in that the edges of an arbitrary VN are connected to the CNs of its local frame the same way as a VN of FS-CSA connects edges to the CNs of a global frame.

IV. DENSITY EVOLUTION ANALYSIS
In the asymptotic regime, i.e., when n → ∞, CSA exhibits a threshold behavior: all users can be resolved if the system operates below a given system load, called threshold and denoted by g . The threshold can be obtained via DE. In this section we derive the DE equations for FA-CSA with boundary effect.

A. Density Evolution for Frame Asynchronous CSA with First Slot Fixed
Because a class-i VN is always connected to a class-i CN, all edges of FA-CSA-F are not equivalent, see Fig. 3. Therefore, we must differentiate between edge types, and thus update p i→i , p i→j , q i→i , and q i→j separately in the DE, where p i→i denotes the erasure probability from a class-i VN to a class-i CN, p i→j denotes the erasure probability from a classi VN to a class-j CN with j = i, q i→i denotes the erasure probability from a class-i CN to a class-i VN and q i→j denotes the erasure probability from a class-i CN o to a class-j VN with j = i.
A message from a class-i VN is in erasure if all incoming messages are in erasure, i.e., for j ∈ J i , where J i is given in (8), and is the average erasure probability of incoming messages from CNs in J i . A class-i CN is in erasure if at least one of its incoming edges carries an erasure message. Equivalently, a message from a CN is not in erasure if none of the incoming r 1 +r 2 −1 messages are in erasure. Therefore, where in (a) we used ρ i→i r1 = P i→i r1 , r 1 = r 1 − 1 and r 1 ← r 1 , andp is the average erasure probability of incoming messages from VNs in K i given in (11). Similarly, for j ∈ K i . Note that q i→i = q i→j , which follows from the fact that P i→i (x) = ρ i→i (x) and P i→Ki (x) = ρ i→Ki (x) which, in turn, follows from the properties of the Poisson distribution (see Lemma 1). For a general user model, however, q i→i = q i→j . DE is now performed by iteratively updating (26)-(31), with p i→i , p i→j , q i→i and q i→j initialized to 1. The PLR at position i can be computed asp i = Λ(q i )q i→i /q i and the threshold g is found by searching for the largest value of g for whichp i converges to 0 for all positions. For a system without boundary effect (26)-(31) are only updated for i > n We remark that exact DE requires n → ∞. This would require to keep track of an infinite number of node classes, which is unfeasible in practice. Therefore, the thresholds computed in Section VI must be seen as approximate DE thresholds. However, we have found that it is sufficient to set n ≈ 100 and run DE over a chain of 20n positions in order to obtain g with good precision. Considering larger values of n does not change the obtained thresholds.

B. Density Evolution for Frame Asynchronous CSA with Uniform Slot Selection
For FA-CSA-U all edges are equivalent and therefore we do not need to consider different edge-types. We denote by p i the probability that an erasure message is passed from a class-i VN and by q i the probability that an erasure message is passed from the class-i CN. It follows that, is the average erasure probability of the incoming messages to a class-i VN. Furthermore, is the average erasure probability of the incoming messages to the class-i CN.
DE is performed similarly to FA-CSA-F by iteratively updating (32)-(35), with p i and q i initialized to 1. The PLR at position i can be computed asp i = Λ(q i ).

V. FINITE FRAME LENGTH ANALYSIS
In the finite frame length regime, CSA exhibits an error floor in its PLR performance for low-to-medium loads g. The EF is due to stopping sets, i.e., graph structures which make the iterative decoder fail.
Definition 3. A stopping set S is a connected bipartite subgraph with all CNs of degree strictly larger than 1.
The EF of CSA is dominated by minimal stopping sets.
Definition 4. A minimal stopping set is a stopping set that does not contain a nonempty stopping set of smaller size.
In this section, we find estimates of the EF by approximating the probability of occurrence of minimal stopping sets. We first introduce some useful notation for a stopping set S.  Table II] along with ν (S), µ (S), and v l (S) for all 31 minimal stopping sets of FS-CSA with µ (S) ≤ 4. Since FA-CSA and FS-CSA share exactly the same stopping sets, these will be used in our evaluation.
If we allow infinitely many decoding iterations (and let n RX → ∞ FA-CSA), all packet losses in CSA are caused by stopping sets. The PLR (see Definition 1) is then equivalent to the probability that an arbitrary VN is part of a stopping set.
We denote by A the set of all stopping sets, and by A ⊂ A a smaller set of minimal stopping sets that dominate the PLR in the EF region. Furthermore, let u denote an arbitrary VN in a CSA system. The PLR can be approximated as follows, In (a) the probability is upper bounded using the union bound.
In (b) we consider a summation over the subset A , turning the upper bound into an approximation. Lastly, in (c) we condition the probability of u being part of a stopping set S on the RV M , representing the number of VNs that can create the stopping set S with u, and average over all possible values of M . Using (36) as a starting point, we derive EF approximations for FA-CSA-FNB and FA-CSA-UNB. We do not consider boundary effects as this simplifies the analysis. Furthermore, we remark that a boundary has negligible impact on the EF of a system that runs for a longer time.
We express Pr (u ∈ S|m) in (36) in terms of factors that are simpler to derive, where a(S, m) is the expected number of ways to select ν (S) VNs with the degree profile v(S) from a set of m VNs with degree distribution Λ(x), b(S) is the number of ways to select the CNs of S such that u ∈ S, c(S) is the number of graphisomorphisms of S, and d(S) is the total number of ways in which ν (S) VNs (including u) with degree profile v(S) can connect edges to CNs in their local frames. The fraction ν(S) m represents the probability that VN u is one of the ν (S) VNs in S. We give first the factor a(S), because it is the same for FA-CSA-FNB and FA-CSA-UNB, which stems from the multinomial distribution and was derived in [10]. In the following, we derive expressions for the factors b(S) and d(S).

A. Frame Asynchronous CSA with First Slot Fixed
Let u represent a VN in the range [i, i+n−1]. Furthermore, to simplify the derivation we make the assumption that S spans at most n slots. Without loss of generality, we consider the range [i, i + n − 1].
Since we are considering stopping sets constrained to the slots in the range [i, i + n − 1] that contain u, the first slot of the stopping set must be i. According to our assumption, the remaining µ (S) − 1 slots of S are chosen with equal probability from the subsequent n − 1 slots. This gives where the subindex FA-F is a short-hand notation indicating that the parameter, in this case b, is for FA-CSA-FNB. Similarly, we will use subindex FA-U for FA-CSA-UNB. We now consider d FA−F (S). An arbitrary active user in slot i + n − 1 has n equiprobable slots for its first replica, i.e., the slots in [i, i + n − 1]. However, the first replica of user u is fixed to slot i. For each placement of a degree-l user's first replica, there are n−1 l−1 possible placements for its remaining replicas. Furthermore, each user places its replicas independently of other users. Thus, An EF-approximation for FA-CSA-F is now given by evaluating (36), using (37)

B. Frame Asynchronous CSA with Uniform Slot Selection
We denote by u an arbitrary VN in an FA-CSA-U system. Without loss of generality we assume that if a VN u ∈ S, then u is the highest degree VN of S. We make a simplifying assumption that all the VNs in S must be active in the entire range [k f , k l ], where k f and k l are the positions of the first and last CNs that u is connected to, respectively, and we let q(S) denote the degree of u.
If we denote by D the RV representing the distance k l − k f , then its probability mass function (pmf) is given by, . According to our assumption, the number of VNs from which the VNs of S can be selected is Poisson distributed with mean g(n − D). We let M ∼ Po(g(n−D)) be the RV representing this number. Then m in (36) is a realization of M such that obtained by averaging over D.
The CNs for S are selected randomly from a set of n CNs corresponding to the local frame of u. Therefore, A degree-l VN can connect its edges in n l ways to its local frame, hence, C. Frame Synchronous CSA The probability Pr (u ∈ S|m) in (37) for an FS system with constant number of users per frame m has been previously derived in [9] and [10]. For completeness, we give here the corresponding expressions of the factors in (37), because the formulation that we use is slightly different and also includes the Poisson user model.
The CNs for S are selected randomly and uniformly from a set of n CNs (corresponding to the n slots of the frame) and thus,

VI. NUMERICAL RESULTS
In this section, we give numerical results on the performance of FA-CSA in the asymptotic and finite frame length regime and give comparisons with FS-CSA and SC-CSA in terms of decoding thresholds, EF, and delay.
We observe that for FA-CSA with boundary effect, the decoding threshold improves significantly with respect to the case where there are already active users at time i = 0. This is due to a boundary effect (thus its name) caused by the lower degree of the CNs for i ∈ [1, n − 1], which results in a wave-like decoding effect similar to that of spatially coupled LDPC (SC-LDPC) codes. Furthermore, for FA-CSA with boundary effect and regular VN-degree distribution Λ(x) = x l , the decoding threshold improves with increasing VN degree, whereas the opposite occurs for the systems without boundary effect. This behavior is similar to that of regular LDPC codes, where a larger VN degree improves the threshold for SC-LDPC codes but has the opposite effect for uncoupled LDPC codes. We also give in Table I the corresponding decoding thresholds for FS-CSA, denoted by g FS . FA-CSA with boundary effect yields significantly better thresholds than FS-CSA. Interestingly, the thresholds for FA-CSA-FNB, FA-CSA-UNB and FS-CSA are identical. Indeed, the systems are very similar in that FS-CSA and FA-CSA-UNB have the same CN-degree distribution and CNs of FA-CSA-FNB have the same average degree, but a slightly different node connectivity. In Fig. 4, we plot the PLR of FA-CSA with boundary effect obtained from DE (dashed lines) together with simulation results for n = 10 5 (solid lines), for Λ(x) = x l with l = 3 and 5, and Λ(x) = Λ (x). The figure shows that the DE equations are in good agreement with the simulations and make apparent the boundary gain for Λ(x) = x 3 and Λ (x).

B. Finite Frame Length Packet Loss Rate and Error Floors
In Fig. 5 we plot the simulated PLR as a function of the system load, g, for FA-CSA-FNB, FA-CSA-UNB and FS-CSA, with Λ(x) = Λ (x) and n = 200. The EF predictions, as derived in Section V, are also shown with dotted lines. We observe that both instances of FA-CSA outperform FS-CSA in both the EF and WF region. Furthermore, FA-CSA-FNB has a lower EF than FA-CSA-UNB, as predicted by the EF approximations. This hierarchy of the EF performance holds in general, i.e., for any n and Λ(x). We remark that FA-CSA with boundary effect (not included in the figure) exhibits the same performance in the EF as FA-CSA without boundary effect if the system runs for a long time. Interestingly, despite the fact that FA-CSA with no boundary effect has the same asymptotic decoding threshold as that of FS-CSA (see Table I), it is apparent from the figure that it exhibits much superior performance in the WF region as compared to FS-CSA. This seems to indicate that FA-CSA without boundary effect has a better scaling of the PLR than FS-CSA in the finite frame length regime.
In Fig. 6 we compare the PLR performance in the WF region of FA-CSA-FB, FA-CSA-FNB, and FS-CSA for Λ(x) = x 3 and frame lengths n = 500, 1600, 10 000, and 100 000. For short frame lengths (n = 500), FA-CSA-FB and FA-CSA-FNB have similar PLR performance, whereas FS-CSA performs worse. When the frame length is increased, however, the FA-CSA system with boundary effect outperforms the system without boundary effect in the WF region, as predicted by the DE thresholds. This is seen already at n = 1600 where the performance of FA-CSA-FB is slightly better as compared to FA-CSA-FNB. This boundary gain increases with the frame length, as observed for n = 10 000 and n = 100 000. The asymptotic performance for FA-CSA-FB and FA-CSA-FNB given by DE is also plotted as dashed lines with the results for n = 100 000. As the frame length is increased, we also notice how the performance of FS-CSA approaches that of FA-CSA-FNB, as predicted by DE and the results in Table I.
We argued previously that the reason systems with boundary effect yield better decoding thresholds is due to the fact that the lower degree CNs at the boundary induce a wave-like decoding effect. This improvement occurs only if the wave can propagate through the entirety of the system. Due to the randomness of the Poisson user model, for finite frame length the experienced load in a window of n slots will sometimes be above, and sometimes below the expected load g users/slot. Such variations are more distinct for short frame lengths. Therefore, the reason that for short frame lengths the performance of FA-CSA with and without boundary effect are similar, may be explained by the fact that the induced wave may be broken by events where the experienced load is large, causing the wave not to propagate further. Once the wave has been broken the FA-CSA system with boundary effect is equivalent to a system without boundary effect. For large frame lengths, instead, the variation of the experienced load is lower and the wave can propagate, improving performance in the WF region.
By careful inspection of Fig. 6, we notice that the performance at a load g ≈ 0.83 of FA-CSA-FNB is better for n = 1600 compared to n = 100 000. This is counterintuitive at first, but might be explained by the same reasoning as above. For particular frame lengths n, the variations of experienced load could be large enough, such that the low peaks with some chance will induce a decoding wave, similar to the wave of a system with boundary effect. To benefit from such events it would be necessary that the frame length n is not too low, which would cause a decoding wave to break soon after its occurrence. If instead the frame length is large, the probability of a sporadic wave's creation would be extremely low due to the low variations of the experienced load. This conjecture is supported by simulation results. For FA-CSA-FNB with n = 1600 at a nominal system load g ≈ 0.83, we have observed a sudden drop of the simulated PLR from a high level down to the level of the EF after a number of slots. After the drop, the PLR remains low for the duration of the simulation, suggesting that a wave is propagating. We remark that this is indeed a sporadic behavior which occurs at different times (with respect to the start of the system) in each simulation round.

C. Finite Frame Length Delay Performance
We compare the delay (see Definition 2) of FA-CSA-FNB, FA-CSA-UNB, and FS-CSA for n = 200 and Λ (x). In Fig. 7 the average and 90th percentile of the delay is depicted for g ∈ [0.1, 1] users/slot. FA-CSA-FNB performs best in terms of average delay and FS-CSA worst. This is expected because a user in FA-CSA-FNB sends its replicas sooner after joining the system than in FA-CSA-UNB and FS-CSA. However, in terms of the 90th percentile, the two FA-CSA systems perform  worse than FS-CSA for g ∈ [0.8, 0.9] users/slot. We remark that the delay is only defined for successfully received packets, and for g ∈ [0.8, 0.9] the PLR is high for all three systems, as seen in Fig. 5. Therefore, in practice, the system would not be operated at these loads.
In Fig. 8, we plot the pmf of the delay, i.e., the probability that a user has a certain delay k, for a system load g = 0.5 users/slot. The results show again that, overall, FA-CSA-FNB provides the best delay performance. Fig. 8 also shows that the maximum delay of FA-CSA is larger than that of FS-CSA. However, the probability of such large delays is very low. In practice, the maximum delay of FA-CSA is limited by the frame length and the memory size of the receiver, whereas the maximum delay of FS-CSA is strictly limited by the frame length. Indeed, the maximum delay of FS-CSA is 2n − 1, whereas the maximum delay of FA-CSA is given by n + n RX . In Figs. 7 and 8 we considered very large n RX in order to not degrade the PLR performance. With a large n RX , the maximum possible delay of FA-CSA can be very large. For applications with strict latency requirements this might be unacceptable. In Figs. 9 and 10 we therefore present a comparison between FS-CSA and FA-CSA-F with a strict delay constraint of δ max  slots.
Definition 5. The PLR of a CSA system with a delay constraint δ max , is the probability that the packet of an arbitrary user is not resolved within δ max slots of joining the system. 1 In Fig. 9 we depict the delay-constrained PLR (according to Definition 5) of FA-CSA-FNB with δ max = 200 and compare it to that of FS-CSA with n = 100, using Λ(x) = Λ (x). We observe that for a given δ max it is possible to find a local frame length for FA-CSA-FNB such that the PLR is strictly better than that of FS-CSA with the same delay constraint. A good choice of n for FA-CSA-F with the maximum delay constraint δ max is, in general, half the length of the delay constraint, i.e., n = δ max /2, as suggested by Fig. 9. This choice provides relatively good performance and outperforms FS-CSA for all considered system loads.
A large memory can also be costly in practice. Therefore, in Fig. 10 we make a fair comparison in terms of memory size n RX of FA-CSA-F and FS-CSA. In FS-CSA the only natural choice of memory size is the frame length n, because a decoder gains nothing from capturing more than one frame simultaneously. For FA-CSA, however, a fixed n RX leaves the choice of local frame length n open. In the figure, we give PLR results for FA-CSA-FNB with Λ (x), n RX = 400, and different local frame lengths n. We also plot the PLR of FS-CSA with n = 400. For almost all system loads, it is possible to find an appropriate n for FA-CSA-F so that it achieves better PLR compared to FS-CSA with the same memory constraint. Note that the advantage of FA-CSA in terms of memory is that it is more flexible, i.e., for a fixed memory length, the local frame length can be varied. If memory size is not a constraint, the PLR performance of FA-CSA is improved by increasing the memory size and adjusting the local frame length.

D. A Comparison with Spatially Coupled Coded Slotted ALOHA
SC-CSA is a frame-synchronous system where a degree-l VN connects one edge to a randomly selected CN from each of l consecutive frames [8]. Furthermore, w + l − 1 frames are grouped into a super-frame. The CNs of the l − 1 first and last frames of the super-frame exhibit a lower average degree, creating a boundary effect in both ends of the super-frame.
In [8, Table I] iterative decoding thresholds of SC-CSA were presented for Λ(x) = x l with l = 2, 3, 4, 5 and 6. Surprisingly, the thresholds of SC-CSA are identical to the thresholds for FA-CSA-FB and FA-CSA-UB in Table I. This is remarkable because the systems are quite different. Indeed SC-CSA is more structured and enforces the spatially-coupled structure, whereas it is inherent to FA-CSA. However, outside of the boundaries, the CN degree distributions of FA-CSA and SC-CSA are identical (albeit a slightly different connectivity for FA-CSA-FB). Therefore, since both systems (with almost identical degree distributions) have a boundary that generates a wave-like decoding effect, similar decoding thresholds are expected.
Because of the similarities between SC-CSA and FA-CSA with boundary effect, we present a comparison of FA-CSA-FB, SC-CSA, and FS-CSA in the finite frame length regime in terms of PLR and delay. In order to make a fair comparison of SC-CSA, FA-CSA-FB and FS-CSA, we need to make some modifications to the system model for SC-CSA as it is described in [8]. For our comparison, we consider that users join the system according to a slot-by-slot Poisson process, where g is the expected number of users to join in a slot. Regular VN-degree distributions are considered, i.e., of the form Λ(x) = x l . Furthermore, the frame length of the SC-CSA system is n/l. A user that joins the system in SC-CSA will send one replica in each of the l following frames, and we say that the user is active during these l frames. This way, the largest span of the replicas of a user is equal for SC-CSA, FA-CSA-FB and FS-CSA. Note that, by definition, the SC-CSA system assumes that there are no active users in the beginning, meaning that CNs of the first l − 1 frames will exhibit lower expected degree than other CNs. We do not terminate the SC-CSA system which would give the CNs of the last l − 1 frames to have lower expected degree too, since this is not done for FA-CSA-FB. In practice, we can assume that the systems run indefinitely and a sliding-window decoder is used. Decoding of SC-CSA is performed in the same way as for FA-CSA. Fig. 11 gives simulation results on the PLR for FA-CSA-FB, SC-CSA, and FS-CSA, for n = 120 and l = 3. As expected, the WF performance of FA-CSA-FB and SC-CSA is similar. However, FA-CSA-FB performs remarkably better than SC-CSA in the EF. In fact, SC-CSA has even worse EF than FS-CSA. The reason for this is that in SC-CSA each replica is forced into a smaller frame of size n/l. This makes the probability that two users select the l same slots for transmission much larger. In fact, this probability can be easily computed and used as an EF prediction for SC-CSA with regular VN degree distribution, which is plotted as the red dotted line in Fig. 11. Additionally, the average and 90th percentile curves for the delay are given in Fig. 12. For SC-CSA and FA-CSA-FB, the delay behavior is similar. Both systems allow a packet to be decoded after the reception of its last replica, which is why the 90th percentile delay is dramatically increased for loads corresponding to the WF-region of the PLR. However, this is not the region of interest, since it corresponds to a high PLR. Note that FA-CSA-FB yields better delay as compared to SC-CSA. This is due to the fact that for SC-CSA a user that joins the system needs to wait until the next frame before sending its first replica. Since the time a user in FS-CSA waits before its first replica is sent is even longer, the delay is even worse for FS-CSA.

VII. CONCLUSIONS
In this paper, we analyzed the asymptotic and finite frame length performance of frame-asynchronous coded slotted ALOHA. We derived the DE that characterizes the asymptotic performance of FA-CSA and analytical approximations of its performance in the EF. If the receiver can monitor the system before users start transmitting or, equivalently, the system can be reinitialized, a boundary effect similar to that of spatial coupling appears, which greatly improves the decoding threshold as compared to that of standard FS-CSA. We show that for finite frame length, FA-CSA with and without boundary effect achieves superior performance than FS-CSA in terms of EF, WF, and delay. Furthermore, we compared the PLR of FA-CSA and FS-CSA with constraints on both the maximum allowed delay and the memory size. FA-CSA is more flexible in terms of frame length and memory size, and can typically be adjusted to outperform FS-CSA. Additionally, we have shown that FA-CSA performs better than SC-CSA in the finite frame length regime, both in terms of EF and delay.