I'm thinking about ways to manage destructible terrain (tiles/blocks) over a network in a multiplayer game. As players destroy or create blocks, these actions must be propagated to other players.

The way I'd originally approached this was to have the player make a change locally (a block is destroyed), notify the server, and have that sent to all clients (block is destroyed in their code). It's a fairly simple scenario but it's an example of how some management is needed. Player A destroys a block, player B also destroys the same block before the server has been notified (from A or B) and had a chance to let everyone know. The message from player A then gets to the server where some checking is performed (server has copy of blocks too, so it really manages actual state) and the message that the block was destroyed is sent out to everyone. The message from Player B (block destroyed) gets to the server next and the server rejects (it knows the block is already gone) and so sends back some form of rejection in a message. Player B accepts the fact that the block is gone, and it gets removed at their end. What I like about this model is that players will see their own changes (destruction/creation/damage) immediately, and then send data to the server for checking, and propagation.

Another approach I'd thought about was to send a message from Player A to the server to request a block is destroyed and if successful the server would notify all players (including A). While Player A had sent a request for block destruction to the server the block would not be destroyed locally until the server responded back. With this approach the main drawback is that local actions are not shown until the server responds which could cause a noticeable delay in local actions.

It seems to me that going with my initial approach is best. I'm just thinking this through so if there are any obvious problems, or better existing solutions/ideas/models please feel free to discuss, it'd be appreciated.

You're mixing up the two scenarios. However you wish to do it, there has to be a check at the server with a response, and not until you get a successful response can you destroy the block at the client. Perhaps i'm misunderstanding, but that's how I see it.

One thing I didn't clarify. Say the block is removed on the originator's (player who breaks a block) machine, we send a message to the server and then we await a response. If, for whatever reason, the server decides that block cannot be removed - it responds with a negative and the block pops back on the originator's game. This leads to complications such as the player potentially walking into the space where the block existing, needing procedures to deal with that.

The problem I have with waiting for a server check before modifying the terrain in the originator's game is the potential delay.

This is why most games where players "compete" for actions (health pickup or whatever) actually play a "pre-action" cue when locally doing the action, and an actual "post-action" cue only when the message comes back from the server.

For example, for the both-players-destroy-a-block scenario, you can draw cracks on the block, but not actually remove it, when the player hits it. Then, when the server says the block is destroyed, you play the crack-and-disappear animation on block fragments. If the server says this didn't work out, you instead play a "denied" sound and let the initial cracks you drew fade out without effect.

Your example is actually a simple case -- if one destroys it at same time as another the actions dont conflict and the result is the same). The server can figure out the double interaction with known methods (one phase to accept actions and another then to resolve) (or actioning immediately and then handling the 'already detsroyed state of the target)

Worse is when the actions conflict (one player tries to destroy the block when the other simultaneously puts a protective shield around it)

Or the interactions are richer -- like instead of destruction one player hits the block from one side causing it to start moving in one direction and simultaneously another player hits it a different direction which is suposed to move the block in a conflicting direction.

If each client preempts the arbitration/decision/result of the complex interaction and shows the wrong thing (not the correct the combined interactions result) then you have that presentation problem and have to backtrack/rubberband/correct visibly.

So like mentioned above, the client presented full result has to wait until the server has resolved the interaction. Some techniques can be used like putting some obscuring element (puff of smoke/bright flash?) immediately to cover the time it takes to talk to the server and then show the (above example) block traveling in the correct resolved/arbitrated direction. The delay of course then is important and why many such interactions just wont be done without ruining the illusion.

Some games it may not happen frequently enough to be significant (the visual patching), while others like ball games (ex- soccer) such events occur constantly.

if one destroys it at same time as another the actions dont conflict and the result is the same

If we assume that there is some score or loot received from being the player that destroyed the block, then the problem is the "hard" problem again. Because the "hard" case is actually so common, and is harder, it ends up being simpler to just treat all conflicts as the "hard case" unless there are pressing gameplay needs to somehow "optimize" specific sub-cases.

Do the rendering part on the client (the block crumbling), but do not remove it. You'll have an invisible wall until the host says 'ok'.