I have some questions about implementing a client/server style architecture as described by Valve and this tutorial.

Q1: Should the server queue up user commands and execute them in order or should it only execute the newest command recieved? Assuming it does queue them, how fast should the server execute them (e.g. should it execute them all in one tic or spread execution out over multiple tics)?

My assumption is to spread execution out over multiple tics, but I'm not sure how to compute the number to execute per tic or the delta time. I actually did try implementing this, but I couldn't come up with a good algorithm. I kept running into issues were the user command history kept growing too large due to the server not executing enough commands per-tic.

Q2: If the server runs out of user commands for a client (e.g. due to lag), then should player logic continue to execute with the last user command recieved or do nothing? My assumption is to do nothing. This question comes from the idea that the buttons last pressed might still be pressed during the next tic.

Q3: Should the client send its entire history of user commands that have not been acknoledged per-tic or should it only send the very latest user command per-tic. This assumes when a user command is acknoledged, then it and all older entries before it will be removed from the clients history.

Q1: Should the server queue up user commands and execute them in order or should it only execute the newest command recieved? Assuming it does queue them, how fast should the server execute them (e.g. should it execute them all in one tic or spread execution out over multiple tics)?

Depends on how you implement your world.

Generally the server doesn't get behind, and if there is a queue it is very short. In many fast-paced games the server operates with a small window of time. It examines the time stamp of an event, and if the event is within the time window it inserts it within the simulation, often seen as "rewinding" time. If the time stamp is older than the window it is expired and discarded. If the time stamp is newer than the window then it is in the future so the person is a cheater.

The server generally lives in the future relative to what the clients see on screen. What the player sees as "now" was actually around 10, 20, or even 100+ milliseconds in the past as far as the server is concerned. The article describes how it works around this in part 4. The "rewinding" aspect kicks in and the simulation is processed as though the event from the past were part of the timeline.

Fortunately for most games simulation processing is extremely fast, it is the rendering and similar tasks that consume the most time. Assuming the developers keep all the simulation data around in a sane format it can be rewound and replayed quite easily. If the developers don't, it is much harder.

Q2: If the server runs out of user commands for a client (e.g. due to lag), then should player logic continue to execute with the last user command recieved or do nothing? My assumption is to do nothing. This question comes from the idea that the buttons last pressed might still be pressed during the next tic.

If it is within the server's window of available time you can insert it. If it is outside the window of time you dump it.

Q3: Should the client send its entire history of user commands that have not been acknoledged per-tic or should it only send the very latest user command per-tic. This assumes when a user command is acknoledged, then it and all older entries before it will be removed from the clients history.

There are many common patterns.

In UDP, a common pattern is to repeat until acknowledged. It looks similar to TCP's sliding windows except it resends the data every time instead of when So packets transmitting events look like this:

--> {#1}

--> {#1}{#2}

--> {#1}{#2}{#3}

--> {#1}{#2}{#3}{#4}

<-- {Ack #3}

--> {#4}{#5}

--> {#4}{#5}{#6}

<-- {Ack #5}

--> {#6}{#7}

If your game is very chatty you may accumulate five or ten small items, in which case you may want to revise your protocol. In practice games usually have either nothing or a single item in the queue, occasionally getting two or three during busy times.

That isn't required, just a common pattern for UDP transmission. Other games use more of a TCP model of sliding windows, assuming that data went through properly but reserving them in a buffer until acknowledge in case retransmission is needed.

Generally modern networks work quite well and desktop boxes seldom have packet issues at UDP's layers. UDP can still have issues, it just is quite infrequent. One system may run for months with no issues, a second system may run reliably for hours with no issues, then have a few odd packets, then return to reliability. A third system may exhibit frequent instability. What is invisible to you is that the first one is talking between computers in the same corporate office building, the second is cross-country to a home computer, the third is someone on their laptop in a train using cellular wireless.

Thank you frob for your very useful write-up! I managed to get the implementation working correctly.

There are actually two separate questions here.

The first is the difference between "level" and "edge" triggers.
For example, for commands that say "I am moving forward" or "I am not moving forward," it's sometimes OK to just use the latest state. This is called "level triggered," presumably from electronics where this is a robust way of dealing with interrupt signals.
For commands like "throw a grenade," you don't want to be in the state of "throw grenades until I tell you to stop throwing grenades" -- instead, these are "edge triggered." Fire once, and if you miss it, it didn't happen at all. (Hopefully you don't miss it.)
So, classifying your commands in level vs edge commands, meaning "use latest state" versus "sequence individual commands," is a useful exercise.

The second is the difference between "client sends controls, and evaluates everything as soon as possible" simulation (where entities will never be exactly in "sync" between client and server,) and "client sends input state for each simulation tick, and server re-seimulates," where entities will be in sync on client and server most of the time, barring packet loss or server-side player/player interactions.
If you implement the latter method, then each simulation tick command state is marshalled in order from the client to the server, and executed in order on the server. When commands go missing, the server can assume that the previous command state is retained (for "level" commands,) but will have to send a correction to the clients because any changes in command input will necessarily lead to diverging simulations.
So, deciding whether you use "latest come, simulate when received," or "well defined simulation ticks with ordered inputs," is something you have to do for your game. The first option allows variable simulation tick rate, which some people still think is a good idea. For example, Unreal Engine uses it. The second option is much more well defined and consistent, and by fixing the simulation frame rate / tick size, you can get more stable physical simulation, too.