This is the experimental HTML rendering of capstract:2611.00070v1. The PDF is the version of record.

On the Enumeration of Removal Requests in Broadcast Threads

Elara J. Selnor
Department of Discrete Mathematics, Orisel Institute of Mathematical Sciences, Veyport
November 20, 2026

Abstract

We study a broadcast thread in which recipients request removal by replying to all, while removal is deferred until no replies remain. Under a memory- rule, a recipient replies to a request unless they occur among its most recent ancestral senders. For a list of participants, the thread terminates if and only if . With full ancestry memory the number of requests is for , although no participant sends twice on a single ancestry. With memory , there are requests at every sufficiently large depth. We derive the depth counts, individual traffic, and the limiting distribution of the number of eligible senders on the ancestry of a uniformly selected request. An atomic shared registry instead admits exactly requests. The counts are verified by explicit enumeration of sender sequences.

Keywords: enumeration, self-avoiding walks, branching, broadcast communication

1Introduction

A participant who wishes to leave a group email thread may request removal by replying to all recipients. If other participants also wish to leave, a removal request can give rise to further removal requests. We consider a list on which every recipient wishes to be removed and on which removal is processed only after the thread has become quiet. The messages being counted are the requests for removal themselves.

The rule for suppressing duplicate requests matters. A participant may avoid sending a second request in the ancestry of a message while still responding to separate branches of the thread. We compare this rule with bounded ancestry memory and with a shared registry that permits only one request per participant across the whole thread. In each case, all requests are sent to the original list; a previously sent request does not remove its sender from the list.

The ancestry of a request is a word over the participant set. With full ancestry memory it is a self-avoiding walk on a complete graph, a setting studied by Slade [3] and Deng et al. [1]. The enumeration of the resulting words also follows from standard constructions for labelled sequences [2]. We use this representation to count requests, deliveries, and the number of people who have already requested removal along a typical ancestry.

The distinction between local and shared memory is substantial. With full ancestry memory the thread stops, but its request count grows factorially. For a list of ten, it contains 986,410 requests before removal can be processed. If only the nine most recent senders in each ancestry are remembered, the thread never becomes quiet. A shared registry reduces the count to ten.

2Model

Let with , and let participant 1 send an initial removal request. Each message is addressed to all other participants. A recipient who is eligible under the chosen memory rule sends exactly one reply to all, also requesting removal. All eligible replies are eventually delivered, and each message retains its own chain of ancestors. Different branches are not merged.

We identify a message at depth with its sender sequence , where . Its parent is obtained by deleting . Every eligible recipient gives a distinct child, so message counts are counts of such sequences, not counts of distinct message bodies. The initial request has depth zero. A delivery is one message received by one recipient; it is distinct from a sent message.

Under the memory- rule, for , a recipient replies if and only if they do not occur among the last senders of the message’s ancestry, or anywhere in that ancestry if it contains fewer than senders. Thus the current sender is always ineligible. The rule is applied separately on every branch. In particular, a request on one branch does not suppress a request by the same person on another.

For we call the rule full ancestry memory. Since there are only participants, no sender can recur on a branch. As a comparison, the shared-registry rule admits at most one request per participant across all branches, using an atomic check when the request is sent. Each of the other participants receives the initial request and sends one reply, so the total is exactly .

These are deterministic counting models. They do not require a probability of replying or a distribution of delivery times. In particular, a pending reply is counted even if a different branch has already produced a request from its sender.

3Counts by depth

Let be the number of messages at depth , and write with .

Theorem 1 (Bounded ancestry memory). For and ,

For full ancestry memory,

Proof. At depth , the last senders are distinct. This is true at the root and remains true when a sender outside that suffix is appended. Every message at depth therefore has exactly children. Multiplying these factors from the root gives Eq. (1). When , the factors are , yielding Eq. (2).∎

Corollary 2 (Termination threshold). The thread becomes quiet after finitely many depths if and only if . For , there are requests at every depth .

Proof. For , every sufficiently deep message has children. At , Eq. (1) reduces to for . For , Eq. (2) eventually vanishes.∎

The threshold includes the two-person case: with memory one, the two participants continue to reply to one another; with full ancestry memory, the second request has no eligible recipient. Figure 1 shows the first six depths for a list of six. Counts at depth six and later are zero under full memory, so they are omitted from the logarithmic plot.

100101102103012345Depth of requestRequestsMemory 1Memory 3Full memory
Figure 1: Requests by depth for six participants under three memory rules. Full ancestry memory has no requests after depth five.

4Full ancestry memory

Denote the total number of requests by . Every request is delivered to recipients, including recipients who have already appeared on its ancestry. Consequently the total number of deliveries is .

Theorem 3 (Total requests). For ,

Proof. The first expression follows from Eq. (2) and the second by setting . For , the omitted tail of is positive and at most : after the first omitted term , successive terms decrease by factors at most . Taking the floor proves the result.∎

Writing for the one-person case, the exponential generating function in the number of non-initiators is

This is the product of the exponential series and the ordinary sequence generating function; it also gives .

Proposition 4 (Individual traffic). The initiator sends one request and receives deliveries. Every other participant sends requests and receives deliveries.

Proof. The initiator occurs at the start of every ancestry and cannot appear again. All non-initiators are interchangeable under permutations that fix participant 1, and together they send the remaining requests. Every message is delivered to all participants except its sender, giving the stated receipt counts.∎

The identity holds for . Thus each non-initiator on a ten-person list sends as many requests as the entire full-memory process on nine people. Table 1 gives exact values; the shared-registry benchmark sends requests in each row.

Table 1: Full ancestry memory. Deliveries count one copy per recipient; each non-initiator’s requests are counted across all branches.
List size Requests Requests per non-initiator Deliveries
3 5 2 10
4 16 5 48
5 65 16 260
6 326 65 1,630
7 1,957 326 11,742
8 13,700 1,957 95,900
9 109,601 13,700 876,808
10 986,410 109,601 8,877,690

5A uniformly selected request

Choose one of the messages uniformly after the full-memory process has finished. Let be the number of participants who have not yet appeared in its ancestry. For , messages with have depth . Hence

Proposition 5 (Remaining eligible senders). As , converges in distribution to a Poisson random variable of mean one. Its exact expectation is

Proof. The probabilities in Eq. (5) tend to , which sums to one. The mean follows by summing for .∎

In particular, the proportion of requests with no eligible sender left on their ancestry tends to . These terminal requests still go to all other participants. They produce no further replies under full memory, but their delivery is part of the traffic.

6Verification and scope

We checked Eq. (1) and Eq. (2) by explicitly generating every sender sequence for , every memory length , and depths through six. All 20 parameter pairs agreed with the formulas. Table 1 was calculated using integer arithmetic from Eq. (3). The plot uses the exact depth counts; there are no sampled observations.

A shared registry removes duplicates across branches, whereas ancestry memory removes them only along a single branch. This is a difference in the scope of the record, not its retention time. The shared-registry comparison assumes atomic admission and reliable delivery of the initial request. It does not model delayed or lost mail, partial participation, departures during the process, or messages with any purpose other than requesting removal. Under the stated rule, removal occurs only after the last request has been delivered; bounded memory with therefore never reaches that point.

References

  1. [1]Youjin Deng, Timothy M. Garoni, Jens Grimm, Abrahim Nasrawi, and Zongzheng Zhou. The Length of Self-Avoiding Walks on the Complete Graph. Journal of Statistical Mechanics: Theory and Experiment, 2019:103206, 2019. doi: 10.1088/1742-5468/ab3da3.
  2. [2]Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, Cambridge, 2009. doi: 10.1017/CBO9780511801655.
  3. [3]Gordon Slade. Self-Avoiding Walk on the Complete Graph. arXiv preprint arXiv:1904.11149, 2019. doi: 10.48550/arXiv.1904.11149.