A FIFO semaphore must reserve a released permit for the oldest waiter. Merely waking the oldest caller is insufficient if a newcomer can consume the permit first. Keep an explicit FIFO queue of private wait records, and transfer the permit directly to the oldest record. Each record has its own monitor, so releasing a permit wakes exactly its chosen recipient.
class FifoBinarySemaphore(initiallyAvailable: Boolean) extends Semaphore {
private final class Waiter { var granted = false }
private val queue = scala.collection.mutable.Queue[Waiter]()
private var available = initiallyAvailable
def down: Unit = {
val mine: Option[Waiter] = synchronized {
if (available) {
assert(queue.isEmpty)
available = false
None
} else {
val w = new Waiter
queue.enqueue(w)
Some(w)
}
}
mine.foreach { w =>
var interrupted = false
w.synchronized {
while (!w.granted) {
try { w.wait() }
catch { case _: InterruptedException => interrupted = true }
}
}
if (interrupted) Thread.currentThread().interrupt()
}
}
def up: Unit = synchronized {
if (queue.nonEmpty) {
val w = queue.dequeue()
// available stays false: this permit is reserved for w.
w.synchronized {
w.granted = true
w.notify()
}
} else {
require(!available, "unmatched binary-semaphore release")
available = true
}
}
}The wait loop is deliberately uninterruptible with interruption status restored after acquisition: abandoning a queued wait record would otherwise strand its reserved permit. A caller that acquires must still complete the buffer operation.
granted is read and written under the wait record's own monitor. The persistent flag prevents a lost wake-up if up runs after registration but before the caller begins waiting. Spurious wakeups simply repeat the loop.The outer monitor serializes registration and the FIFO queue. A caller either consumes a genuinely free permit when nobody is queued, or appends one record.
up removes exactly the front record and leaves available false, even if its owner has not yet resumed. A newcomer must queue behind existing records instead of stealing the handoff. The outer-to-inner lock ordering in up is safe because waiting callers release the outer monitor before acquiring their private monitors; no caller holds a private monitor while trying to reacquire the outer one.private val empty: Semaphore = new FifoBinarySemaphore(true)
private val full: Semaphore = new FifoBinarySemaphore(false)This is a complete implementation when inserted in
SemaphoreMemory: its write and read methods remain exactly the displayed methods. Pending writers obtain empty-slot permissions in registration order on empty; pending readers obtain full-slot permissions in registration order on full. Each handoff permits just one caller to access the slot, soFirst-come-first-served means the order in which concurrent calls register under the monitor; two overlapping calls have no externally determined order. The guarantee is separate for the two kinds of caller. A global order combining reads and writes cannot be required: an initial read must wait while a later write supplies its value. Subject to eventual scheduling and the arrival of matching operations of the opposite kind, no registered caller is overtaken by a later caller of its own kind. The design avoids broadcast wakeups as well as barging.Give the two waiting predicates different semaphores.
empty has one permit initially; full has zero. A writer takes the empty permit before touching the slot and transfers permission to a reader by releasing full. A reader does the reverse.class SemaphoreMemory[T] extends Memory[T] {
private val empty: Semaphore = new CountingSemaphore(1)
private val full: Semaphore = {
val s = new CountingSemaphore(1)
s.down
s
}
private var slot: Option[T] = None
def write(msg: T): Unit = {
empty.down
slot = Some(msg)
full.up
}
def read: T = {
full.down
val result = slot.get
slot = None
empty.up
result
}
}For a single slot, a separate mutex around
slot is unnecessary. There is a unique circulating permission: either an empty permit is available, a writer holds it, a full permit is available, or a reader holds it. During the transition the sum of available permits can be zero; it is never necessary to assert that it is always one. In particular, the next writer cannot start until the preceding reader has finished reading, cleared the slot and released empty.The monitor operations inside each semaphore also establish the required happens-before relation: the write precedes
full.up, and a successful subsequent full.down makes it visible to the reader. Likewise, the reader's clearing precedes the next writer's successful empty.down. Slot accesses therefore need no unsynchronized visibility assumption. The invariant isOnly writers wait on empty, and only readers wait on full. With the single-notification semaphore implementation in part (a), a state change wakes at most one waiter of the appropriate kind, avoiding the thundering herd of part (i). This is an efficiency improvement, not yet a first-come-first-served guarantee.If one or more readers arrive before the first writer, they block on the initially unavailable
full semaphore. Their waits release its monitor, so they do not prevent a writer from obtaining the independent empty permit. The first write releases full and permits exactly one reader to take that value. Remaining readers wait for later writes; they never see uninitialized storage.Use one monitor to protect both the occupied flag and the slot.
Option supplies an empty marker without confusing an empty slot with a valid null payload.class MonitorMemory[T] extends Memory[T] {
private var slot: Option[T] = None
def write(msg: T): Unit = synchronized {
while (slot.nonEmpty) wait()
slot = Some(msg)
notifyAll()
}
def read: T = synchronized {
while (slot.isEmpty) wait()
val result = slot.get
slot = None
notifyAll()
result
}
}A writer changes empty to full while holding the monitor; a reader changes full to empty while holding the same monitor. The corresponding successful assignment or removal is its linearization point. No second writer can overwrite a full slot, and no two readers can remove one value. Rechecking in a
while handles spurious wakeups and competition after notification.There are two different waiting predicates on the same monitor: writers need empty, readers need full. A single arbitrary
notify could wake a caller of the wrong kind. For example, after a reader empties the slot, waking another reader leaves it waiting again while a writer remains asleep, potentially stranding the computation. notifyAll prevents that lost wake-up pattern by allowing every waiter to recheck. Thus,With many users, each change wakes numerous software threads even though at most one can use that new slot state. Most reacquire the monitor, find their predicate false and sleep again. This thundering herd wastes context switches and lock acquisitions. It also supplies no fairness or arrival-order guarantee.Run two
dfFringe producers on synchronous one-to-one message-passing channels, and compare one received leaf from each. Catch closure separately on each input: otherwise the first closure could hide an extra value in the other fringe. An extra value or unequal pair is enough to stop immediately.def sameFringe(node1: Array[Node], root1: NodeId,
node2: Array[Node], root2: NodeId): Boolean = {
val a = OneOne[NodeId]
val b = OneOne[NodeId]
var equal = true
def next(p: ?[NodeId]): Option[NodeId] =
try { Some(p ? ()) }
catch { case _: io.threadcso.process.Stopped => None }
val compare = proc {
var done = false
try {
while (!done) {
val x = next(a)
val y = next(b)
(x, y) match {
case (None, None) => done = true
case (Some(u), Some(v)) if u == v => ()
case _ => equal = false; done = true
}
}
} finally { a.closeIn; b.closeIn }
}
(dfFringe(node1, root1, a) || dfFringe(node2, root2, b) || compare)()
equal
}After successful comparisons, the first identities in the two leaf sequences agree. The first differing pair disproves equality of sequences; simultaneous exhaustion proves it; exhaustion on exactly one side disproves it. Therefore,Closing both inputs on every comparator exit releases either producer if it is waiting in an output. The closure handler in
dfFringe then returns normally, and the parallel composition joins before equal is read. For finite trees and eventual scheduling, the comparator's next read either obtains a leaf or observes completion, so there is no deadlock caused by reading the two inputs in a fixed order.Only a constant amount of leaf data is stored. After an early mismatch, each producer may already have traversed toward its next leaf and be blocked offering it; cancellation prevents unbounded speculation or deliberate construction of the remaining fringe. Occasionally a short unequal fringe is already completely traversed when its final distinguishing value is compared. The streaming guarantee is that neither complete fringe needs to be materialized in advance, and work stops as soon as inequality is established.
Use the recorded child list as the depth-first traversal order. A leaf of a tree has no children, so it contributes its own identity once. Closure cancels the remaining traversal; a normal completion closes the output so that a consumer can detect end-of-fringe.
def dfFringe(node: Array[Node], root: NodeId, fringe: ![NodeId]): PROC = proc {
def walk(v: NodeId): Unit = {
val cs = node(v).children
if (cs.isEmpty) fringe ! v
else cs.foreach(walk)
}
try { walk(root) }
catch { case _: io.threadcso.process.Stopped => () }
finally { fringe.closeOut }
}A completed finite spanning tree has no recursive child graph cycle, so this visits a finite number of vertices. A blocked leaf send is released if its output closes. A singleton root is itself a leaf of a tree and is output once. With sufficient call-stack space,
Use one logical traversal token carrying the discovered vertex set and the active LIFO stack of vertices. The current vertex either discovers its first still-unvisited outgoing graph neighbour, or returns to its preceding stack entry. The former records both the child's parent in a rooted tree and the parent's child. Unlike concurrent flooding discovery, this visits one entire branch before the next, giving an actual depth-first search.
The important directed-graph detail is that a child's parent need not be an outgoing graph neighbour. Return the token by routing it through the original directed graph; a routing hop does not count as a traversal visit. The following duplicate-suppressed flooding route requires no previously known topology and sends only to immediate outgoing graph neighbours.
final case class Token(visited: Set[NodeId], stack: List[NodeId], serial: Int)
sealed trait Msg
final case class Route(serial: Int, target: NodeId, token: Token) extends Msg
case object Finished extends MsgHere
stack.head is the current vertex. Use the same paired toNode and fromNode ports as in (i), now with the new Msg type. Set mailbox capacity to , normalize neighbours with distinct, and again leave the mailboxes open until all processes have joined. The following helpers are local functions inside each node's generated process.def span: PROC = proc {
val adj = neighbours.distinct
val routed = scala.collection.mutable.Set[Int]()
var entered = false
var done = false
def flood(message: Msg): Unit =
for (w <- adj) toNode(w) ! message
def move(target: NodeId, state: Token): Unit = {
val s = state.serial + 1
routed += s
flood(Route(s, target, state.copy(serial = s)))
}
def step(t: Token): Unit = {
assert(t.stack.head == me)
if (!entered) {
entered = true
parent = if (t.stack.tail.isEmpty) me else t.stack.tail.head
children = Nil
}
adj.find(w => !t.visited(w)) match {
case Some(w) =>
children = children :+ w
move(w, Token(t.visited + w, w :: t.stack, t.serial))
case None =>
t.stack.tail match {
case p :: rest => move(p, t.copy(stack = p :: rest))
case Nil => flood(Finished); done = true
}
}
}
if (me == 0) step(Token(Set(0), List(0), 0))
while (!done) {
fromNode(me) ? () match {
case r @ Route(s, target, t) =>
if (!routed(s)) {
routed += s
if (target == me) step(t) else flood(r)
}
case Finished => flood(Finished); done = true
}
}
}Every route number is globally unique: there is one logical token, and its serial increases at every move. The sender inserts that serial in its own
routed set before flooding; this stops a returning copy from circulating again. Intermediate vertices forward the first copy of an envelope and ignore later copies. Its target consumes exactly one copy without forwarding it. Because the directed graph is strongly connected, a simple directed path from sender to target exists; its intermediate vertices eventually relay the envelope. Thus each move eventually finishes.A routed return can pass through a vertex not yet discovered by the depth-first search. That vertex only forwards the envelope: it does not run
step, change entered, or assign a parent. This distinction is essential. For the directed cycle , returning from two to one uses , while the logical traversal stack changes from to .
A depth-first search return follows a routed directed path when the child has no reverse directed edge
. Details. The discovered vertex set only grows. Each newly discovered vertex is pushed once and later popped once; an exhausted vertex can never acquire a new unvisited neighbour as this set grows. Consequently there are exactly downward moves and return moves. When the root exhausts its outgoing graph neighbours, every vertex has been visited, by the standard reachability argument for depth-first search. Each nonroot parent was recorded along the actual downward directed edge, and
children records exactly those assignments in discovery order.There are route envelopes, each forwarded at most once per outgoing directed edge, and one final
Finished flood. Each node forwards Finished before exiting; strong connectivity therefore delivers it everywhere. There are at most total messages into any mailbox, below the proposed capacity. Even a mailbox whose process has already exited cannot block later sends. All processes terminate withThis deliberately trades communication efficiency for a simple valid solution on a genuinely directed graph. A direct parent acknowledgement would instead require an additional bidirectional-edge assumption, which the question does not supply.A directed graph needs an explicit termination argument. After assigning its parent in a rooted tree, a vertex must still receive later traffic: having no new graph neighbours to discover is not proof that other senders have finished. Use a discovery wave together with duplicate-suppressed announcements of activated vertices. Both kinds of message identify their immediate sender, who has already activated.
sealed trait Msg { def from: NodeId }
final case class Discover(from: NodeId) extends Msg
final case class Active(from: NodeId, origin: NodeId) extends MsgLet
adj = neighbours.distinct. The actual communication objects must expose both input and output ports: the paper's Seq[![Msg]] annotation supplies only output capabilities, although the following sentence also requires receiving. Set up one shared-writer, single-reader buffered message-passing channel per vertex, publish its output in toNode, and keep its input in fromNode. Only node i reads fromNode(i). These are the two ports of the same underlying mailbox, not additional graph edges. The question's prohibition on buffered message-passing channels applies to Question 1(a), not to this question.Take , reliable delivery, eventual scheduling, finite
adj, and mailbox capacity . Every node has at most distinct incoming neighbours, including itself if there is a self-loop. The bound below ensures that no send blocks merely because a mailbox's receiver is not currently reading. Do not close these shared mailboxes on local process termination: late, redundant traffic is harmless and bounded. Their creator can release them after the parallel composition has joined. For example, the concrete setup can useval mailbox = Vector.fill(N)(N2NBuf[Msg](B, 0, 1))
val toNode: Seq[![Msg]] = mailbox
val fromNode: Seq[?[Msg]] = mailboxHere the zero writer count makes the shared output independent of individual writer departures; processes do not call its
closeOut during the search.def span: PROC = proc {
val adj = neighbours.distinct
var started = false
val known = scala.collection.mutable.Set[NodeId]()
def announce(origin: NodeId): Unit = {
if (!known(origin)) {
known += origin
for (w <- adj) toNode(w) ! Active(me, origin)
}
}
def activate(sender: NodeId): Unit = {
started = true
parent = if (me == 0) 0 else sender
for (w <- adj if me == 0 || w != parent)
toNode(w) ! Discover(me)
announce(me)
}
if (me == 0) activate(0)
while (known.size < N) {
val message = fromNode(me) ? ()
if (!started) activate(message.from)
message match {
case Discover(_) => ()
case Active(_, origin) => announce(origin)
}
}
}An announcement may be a vertex's first incoming message. It then serves as a discovery message too: its immediate sender is already active, and the receiving vertex adopts that sender as its parent in a rooted tree before forwarding anything. This preserves the required first-message rule. In particular, an inactive vertex never forwards announcements while remaining inactive, which could invalidate the parent-order argument.
For each nonroot vertex, its parent in a rooted tree activated strictly earlier. Repeated parent-following therefore cannot make a graph cycle and eventually reaches the unique initially active vertex, zero. Each parent assignment uses an actual incoming directed edge. Strong connectivity ensures eventual activation of every vertex: if an activated set were proper, a directed path from zero to an inactive vertex would have a first edge leaving that set. Its sender sends a discovery message along that edge; excluding its own parent does not exclude an inactive neighbour.
Each activation sends at most one
Discover on each outgoing directed edge. For each of the origins, each vertex forwards Active at most once on each outgoing directed edge. Therefore a mailbox receives at most messages over the whole run, proving the chosen nonblocking storage bound. Each origin's announcement eventually reaches every vertex, since every first receipt forwards it on all outgoing directed edges. Thus every known set reaches size and every process terminates, even if redundant messages remain unread:No timeout is used to conclude that the distributed work has finished. This uses larger finite mailboxes to make the termination proof simple, rather than assuming that simultaneous synchronous broadcasts cannot deadlock.In the displayed network, the first cells retain values and cell is still in its initial state. It accepts only a value in , so it cannot accept the incoming sentinel value. For the first cell blocks the external sentinel value; for a stored cell blocks while trying to pass it to an empty neighbour. ThusTo handle shorter inputs, add an empty-cell branch to the initial state. An empty cell then terminates the downward scan and immediately returns an empty sequence. Earlier occupied cells append their retained values exactly as before; later cells need not participate. This works for every , because the occupied prefix of the chain alone produces the required output. For , the original sentinel-only tail still supplies the empty suffix. Every cell receives the same modification.
Past exam of the computer science course of the University of Oxford 2015 Concurrency 1 d i Solution 2026-10-31
Use a chain of identical storage cells, each retaining the first value it sees and passing later values to the next cell. On the return journey it passes the next cell's reversed output before emitting its own retained value. This turns the chain into a distributed LIFO stack.
Here is one cell template. Its ports carry incoming values towards the tail; carry returning values towards the front. Each port carries values in , with the sentinel value outside :An input such as abbreviates an indexed CSP external choice over the corresponding CSP events. An output is the CSP prefixing action . There is no extra controller process.
For , take copies of this same template. Introduce channels for and apply port CSP event renaming to copy , for , as follows:At the front put and . Adjacent cells synchronize on every shared or CSP event. The two tail channels are sentinel-only: and are local tail CSP events, with no other participant required. Disable all for . Formally, use a partial relational CSP event renaming for the last copy, omitting the pairs for its with ; an unmapped transition is blocked. This explicitly prevents a fictitious tail from generating data.
Let be the resulting port-renamed cell and its visible alphabet. With consisting of the internal link CSP events, including the two tail CSP events, the answer isHere the indexed operator is CSP alphabetized parallel composition: each CSP event is synchronized by all cells whose alphabets contain it. There are exactly storage-cell processes; port wiring and the sentinel-only tail adapt their interfaces, without adding a helper process. The local tail CSP events are hidden, as are all inter-cell communications.
To see correctness, after inputs have propagated, cell retains . The input sentinel value propagates to the tail. The last cell performs its two local tail CSP events, then returns . Inductively, if the suffix after cell returns , cell relays those values, replaces the final sentinel value by , and stops. Hence the external output isand starts only after . Shared links provide synchronization rather than an assumption that all cells take steps simultaneously. For the degenerate known-empty input, no storage is needed: the interface is simply .
The stated ability is a complete failure of second-preimage resistance. Given an arbitrary target message , compute with . Ask the signer for a digital signature on only, obtaining . Thenso is a forgery of the chosen target. The inequality ensures that the adversary has not requested the target's own digital signature.
Under a known-message signature attack, the same weakness also gives an existential forgery: take an observed signed , find its different second preimage, and reuse the digital signature. The universal forgery claim uses the stronger chosen-message signature attack capability to request the companion of whichever target was specified.
Choose any candidate digital signature , compute , and invoke the granted algorithm to find with . Output . Every chosen now leads to a valid message, with no need to search for a digest on which inversion happens to work.
This is stronger coverage than the generic failure discussed in solution, but it does not by itself give a universal forgery. For a target message fixed beforehand, the adversary needs satisfying , which inverts the trapdoor map . Inverting instead produces some message for a chosen digest and does not compute that .
Nor does an arbitrary preimage algorithm necessarily produce a message different from when invoked on : it may return itself. Thus a universal forgery under a chosen-message signature attack needs an additional alternative-preimage guarantee, precisely the distinction supplied in solution.
A failure of collision resistance supplies distinct messages withAsk the legitimate signer to sign , obtaining . Output without ever requesting a digital signature on . Its verification succeeds becauseThusThe adversary chooses the collision pair, but cannot in general insist that one member equal an independently specified target. A known-message signature attack would require the stronger ability to collide with an already signed message; finding an arbitrary collision alone does not provide that.
The standard attack on this raw trapdoor construction chooses a candidate digital signature first, computes , and uses a failure of preimage resistance to find with . Thenso verifies. The resulting message is selected by the inversion procedure, rather than being an arbitrary prescribed document. This is an existential forgery under a key-only signature attack whenever the inversion weakness applies with nonnegligible success to those sampled digests.
The phrase “fails to be preimage resistant” must be read with its target distribution. Since is a permutation, uniform gives a uniform -bit digest; if inversion works only on a tiny identifiable exceptional set, this sampling method need not be feasible. Merely knowing a valid signed message and recovering that same message from its digest is not a new forgery. Producing a different message there requires a failure of second-preimage resistance. Part solution removes the coverage qualification by explicitly granting inversion at every digest.
For encrypt-and-authenticate, the transmitted pair is with . The recovery map is public, so any observer computesNo symmetric key, exhaustive key search or oracle is needed. Publishing this message-recovery digital signature reveals the entire plaintext and breaks cryptographic confidentiality outright. A digital signature of a suitable digest would have different leakage properties, but the printed construction signs the raw block.
For encrypt-then-authenticate, choose any -bit string and computeSend . The receiver's correct check for this composition is before decryption, so it passes by construction. The receiver obtains a plaintext , although the adversary may not know it.
The finite domains justify the signature relation: is the identity on messages, so is injective and therefore bijective. Hence and also is the identity. The chosen is therefore exactly , without the adversary ever evaluating .
This is a key-only signature attack against raw unrestricted trapdoor signing. It does not invert at a chosen target and does not contradict the assumption that signing an independently specified new message is hard. It exploits choosing the digital signature first. The observation concerns the paper's raw construction, rather than every encrypt-then-authenticate scheme.
For authenticate-then-encrypt, write the intercepted pair as , where . Each trial key givesThe adversary can check the public relationThe true key always passes. An incorrect key will generally fail, and further intercepted pairs can eliminate accidental matches. This gives a ciphertext-only attack with a useful key-testing predicate even when the plaintext has no recognisable format. It makes exhaustive key search applicable with less prior information; it does not reduce the generic key-space size below .
The usual approximate false-pass chance is an ideal-behaviour estimate, not a consequence of the bare permutation identities alone. The decisive point is that the encrypted digital signature supplies publicly checkable redundancy once a candidate decryption key is tried.
Let be the effective mask. For each position ,Thus the mask is always a palindrome, even though itself is uniformly random. The exclusive or of the ciphertext bits in a mirror pair isbecause the equal mask bits cancel. The observer learns the corresponding plaintext parity exactly. If is odd, the middle mask bit is also zero, so the middle plaintext bit is exposed directly.
An explicit failure of perfect secrecy works for every . Choose uniformly from and . For , the ciphertext is a palindrome with probability one. For and , toggling just the first bit breaks the mirror equality, so the ciphertext is a palindrome with probability zero. For , the effective mask is zero and . Observing therefore distinguishes these two messages perfectly.
There are only possible effective masks, each equally likely. Hence even a fresh -bit key supplies at most independent masking bits in this construction. Choosing a long, uniform, one-use key is insufficient if the encryption transformation collapses its randomness.
Perfect secrecy means that observing the ciphertext changes no probability concerning the plaintext. For every distribution of the message , and every with ,Equivalently, for every pair the conditional probability distributions of the ciphertext are identical:The randomness here comes from independent key generation and any encryption randomness. The claim is information theoretic: unlimited computation cannot extract information about from beyond what was known beforehand.
Bob especially needs unpredictability, because is intended to be secret until Tim processes the request. A predictable counter destroys even that limited assurance.
If the adversary knows Bob's next value , it initiates a run with Alice's name and intercepts Bob's request. Without consulting Tim, it chooses a key , constructs , and sends as message 3, with any suitably shaped opaque ticket for Alice. Bob cannot inspect that ticket. He accepts , sends message 4, and accepts the adversary's . Alice and Tim need not participate.
This preplay attack requires a correct prediction of Bob's outstanding value, knowledge of his public key, and the ability to intercept or race the genuine response. Observing an earlier unencrypted response may expose a counter value from which to predict the next. With an independent uniformly random hidden -bit value, blind prediction succeeds with probability per attempt.
In particular, random cryptographic nonces do not make the printed protocol sound. After the genuine message 3 reveals , the adversary can use exactly the substitution in solution. Predictability allows an earlier attack without Tim; lack of response binding allows an attack even with perfect unpredictability.
An unpredictable random -bit cryptographic nonce is better for Alice than a predictable counter, provided repetitions are detected or made sufficiently unlikely. Alice wants a matching ticket to imply a response to her present challenge, and the protocol lets anyone ask Tim for a ticket containing a chosen .
Suppose an adversary predicts that Alice's next challenge for Bob will be . Before Alice starts that run, the adversary sends to Bob as message 1. Bob asks Tim for a session key and returns the genuine pair in message 4. The adversary stores that pair and lets the early run lapse. Later, when Alice really emits , the adversary blocks it and delivers the stored pair. Alice's ticket and greeting checks pass, despite the key and Bob's participation predating her run. This is a preplay attack on freshness and recent participation. Bob need not accept Alice's eventual message 5 for Alice's acceptance to have failed its freshness goal.
Success requires the predicted value and identities to match, an early run that yields the matching ticket and greeting, and Alice to accept solely from the outstanding value without additional expiry or run binding. No session key disclosure is needed to defeat freshness; if that old key has also been compromised, impersonation and loss of cryptographic confidentiality follow as well.
A guess at a particular uniformly random value has probability per independent attempt, with success approximately for distinct guesses when that ratio is small. Random choice does not itself guarantee uniqueness: among independent values the birthday problem collision scale is approximately . Counter uniqueness and unpredictability are different requirements.
There are unlisted articles, also show them or only show them.