, computers.
So, that in mind, this pile of combinators and wires is what I came up with:
- async_multiplexer_transmitter.png (930.79 KiB) Viewed 1755 times
Idle - Do nothing until a transmission is requested
Send - Wait for any collisions on the network to resolve, then enter "Contend" mode
Contend - Repeatedly attempt to transmit data
Yield - Temporarily suspend transmission attempts
Machine Components:
Output - Just a wire attached directly to every transmitter and receiver
Input - A wire attached to whatever provides the data (the current value will be what gets sent on a successful transmit and may differ from what it was when the transmission was initiated)
Transmitter - Combinator which pushes the data out
Initiator - Sets the transmitter into send mode if it is not already in send mode.
Memory - Single-entry Memory cells for easily storing "Send", "Contend", and "Yield" states
Repeater - Causes the transmitter to continue attempting to transmit
Finalizer - Detects successful transmission and resets the transmitter (return to Idle mode)
Arbiter - Causes the transmitter to Yield at pseudo-random intervals
Resumer - Cancel Yield state either if every Contending transmitter has Yielded or if any other transmitter has successfully transmitted.
Reserved signals are 'S', 'T', 'I', 'C', 'K', and 'Y'. 'I' is used as the transmitter's Unique ID, 'K' is for the clocK signal, 'T' is used to detect silence and collisions (number of simultaneous transmissions), and 'C' is used to detect network activity. The other two were just me being a lazy designer, letting internal control signals leak into the output. ('S' for Send, 'T' for Transmit, 'I' for Identifier, 'C' for Contend, 'K' for clocK, and 'Y' for Yield).
A unique ID for each transmitter is required and should be included with the input signal. It used the 'I' signal for this. The ID is used to by the arbiter for a pseudo-random backoff sequence that is guaranteed to differ if any pair of IDs within a valid range differ (ID + global clock signal modulo a set prime numbers, in parallel, yielding any time the result is a zero).
Collisions are detected by reading the 'T' signal to determine how many transmitters are attempting to transmit. If the value is one, then it's a valid transmission. Zero is silence. Anything greater than one is a collision.
Transmission within a reasonable time-frame is guaranteed: If the network is busy, all newly requested transmissions will be delayed until after the collision is fully resolved.
Receivers are much simpler: Just a standard component which forwards all valid signals to your signal handler (for convenience, the blueprint receiver includes the Transmitter ID and filters out all other control signals).
A global clock must be attached to the network somewhere. The one in my blueprints only increments during collisions, but a counter which simply increments once per cycle will also work.
Here is the blueprint book containing all three components.
The components from the blueprint book should be wired up like so:
Async-Multiplexer Test Setup
Disclaimer #1: Special care should be taken when extending the network. The arbiter uses modular arithmetic with prime numbers to desynchronize contending transmitters. If you have more than 5005 transmitters and don't adjust the arbiter (either by using larger primes or by adding extra pulse generators with different primes), it will be unable to desynchronize transmitters with IDs which are separated by the product of all prime numbers used (which would completely lock up the network if any pair of them should generate a collision). Disclaimer #2: My design was hacked together very quickly from memory, has not been tested thoroughly, and may contain subtle defects which may cause problems which Eketek refuses to be blamed for. Please do not use it to dispatch ambulances... unless it's an emergency.
EDIT: Upon further review, it turned out that the above multiplexer is flawed: I forgot to implement logic to prevent all unyielded transmitters from yielding simultaneously. That slows the network down unnecessarily and causes large collisions to deadlock. Here is a reworked version with the correct logic:
Async Multiplexer v0.2.1