TCP State Machine

Track: Protocols and sockets. 6 stages. Languages: Go, Python, JavaScript, Rust.

Even though the name says TCP, there is no networking here. No sockets, no timers, and no threads running in the background. You build a small pure function that lives only in memory. You call it with one event at a time, and it tells you what to do and what state the connection is now in.

This models the real decision making inside TCP, the protocol that lets two computers talk to each other reliably. The state names here (CLOSE_WAIT, TIME_WAIT, and so on) are the same ones you would see if you ran netstat on a real machine. You are building the logic that decides when to move between them, not the networking around it.

Implement New(role) and Event(ev) -> (actions, state) using your language's names. role is either "active" (your side starts the connection) or "passive" (your side waits for one).

• Events your code receives: three come from your own program, app_listen, app_connect, app_close. Five act like a message arriving from the other side, seg_syn, seg_syn_ack, seg_ack, seg_fin, seg_rst. One, timeout_msl, is a timer that has already finished.
• Actions your code can send back: send_syn, send_syn_ack, send_ack, send_fin, send_rst, or none at all.
• There are eleven states in total. Each stage below introduces the ones it needs, with a plain explanation and a small picture.

Standard library only.

Where it is used

• Linux, macOS and Windows run this state machine for every TCP connection. The states you build are the ones ss on Linux prints.
• Linux firewalls (connection tracking) watch connections that pass through them, keep their own similar list of TCP states, and use a separate timeout for each one.
• A server that shows thousands of connections stuck in CLOSE_WAIT has a program that got the other side's FIN but never closed its own side. Knowing the states tells you where to look.

Stages

ts1: three-way handshake, both roles (very easy)

You start in CLOSED, nothing has happened yet. The side that starts the connection:

CLOSED --app_connect/send_syn--> SYN_SENT --seg_syn_ack/send_ack--> ESTABLISHED

The side that waits for one:

CLOSED --app_listen--> LISTEN --seg_syn/send_syn_ack--> SYN_RCVD --seg_ack--> ESTABLISHED

SYN_SENT means you asked to connect and are waiting for an answer. SYN_RCVD means someone asked to connect to you and you are waiting for their final confirmation. ESTABLISHED means the connection is open and ready to use. Example: New("active"), then Event("app_connect") returns (["send_syn"], "SYN_SENT"), then Event("seg_syn_ack") returns (["send_ack"], "ESTABLISHED").

The tester will verify: starting the connection from either role ends in ESTABLISHED, sending the right actions along the way.

ts2: the other side closes first (easy)

The other side can ask to close before you do.

ESTABLISHED --seg_fin/send_ack--> CLOSE_WAIT --app_close/send_fin--> LAST_ACK --seg_ack--> CLOSED

CLOSE_WAIT means the other side said it is done, but you have not said you are done yet. LAST_ACK means you have now said you are done too, and you are waiting for the last confirmation. Example: from ESTABLISHED, Event("seg_fin") returns (["send_ack"], "CLOSE_WAIT"). Later, Event("app_close") returns (["send_fin"], "LAST_ACK"), and Event("seg_ack") returns ([], "CLOSED").

The tester will verify: the other side's close request moves you to CLOSE_WAIT, and closing from there goes through LAST_ACK on the way to CLOSED.

ts3: you close first, then wait a bit (medium)

When you ask to close before the other side does:

ESTABLISHED --app_close/send_fin--> FIN_WAIT_1 --seg_ack--> FIN_WAIT_2 --seg_fin/send_ack--> TIME_WAIT --timeout_msl--> CLOSED

FIN_WAIT_1 means you said you are done and are waiting for that to be confirmed. FIN_WAIT_2 means that confirmation arrived, and now you are waiting for the other side to say it is done too. TIME_WAIT means both sides are done, but you wait a little while before fully closing, in case an old message from this connection is still on its way. Example: from ESTABLISHED, Event("app_close") returns (["send_fin"], "FIN_WAIT_1"). Once the other side finishes too, you reach TIME_WAIT, and only Event("timeout_msl") moves you on to CLOSED.

The tester will verify: you reach TIME_WAIT and stay there until the timeout event arrives. You never jump straight from the close exchange to CLOSED.

ts4: both sides close at the same time (hard)

Sometimes both sides ask to close before hearing back from each other.

FIN_WAIT_1 --seg_fin/send_ack--> CLOSING --seg_ack--> TIME_WAIT

CLOSING means you asked to close, and before that was confirmed, the other side also asked to close. Example: from FIN_WAIT_1, Event("seg_fin") returns (["send_ack"], "CLOSING"). Then Event("seg_ack") returns ([], "TIME_WAIT").

The tester will verify: a close request from the other side while you are in FIN_WAIT_1 goes to CLOSING, not FIN_WAIT_2, and CLOSING moves on to TIME_WAIT once your own close is confirmed.

ts5: resets and unexpected events (hard)

A reset, seg_rst, means the connection is being torn down right away, with no more waiting. After a reset, you move straight to CLOSED. Some events do not make sense for the state you are in, for example a message arriving for a connection that was never opened. Never crash on one of these. Follow the normal TCP rule for each case: either ignore the event and stay where you are, or send back a reset. Example: in LISTEN, Event("seg_rst") returns ([], "LISTEN"), since nothing was open yet, so there is nothing to reset. In SYN_SENT, Event("seg_rst") returns ([], "CLOSED"), since your connection attempt was refused. Starting fresh in CLOSED, Event("seg_ack") returns (["send_rst"], "CLOSED"), a message for a connection that does not exist gets a reset sent right back.

The tester will verify: your machine answers resets and unexpected events the same way as our solution in every state, and never crashes.

ts6: event speed (L2, hard)

Keep Event fast, even when it is called many times in a row. Example: if our solution takes 100 ms for a batch of calls, the limit is 150 ms, which is 1.5 times as long. Your solution must also make no more than 2 times as many memory allocations as our solution.

The tester will verify: your code takes at most 1.5 times as long and makes at most 2 times as many memory allocations as our solution, with every answer still correct.

Rules

• Standard library only. Event is a plain function call: no sockets, no timers, no threads.
• Return the actions your machine sends back and its new state on every call to Event.
• An event that makes no sense for the current state must never crash your machine. Follow the normal TCP rule: ignore it and stay put, or send back a reset.

Read the TCP State Machine notes in the wiki