Disclaimer; I'm not the best network programmer, so take this with a grain of salt.

First of all, you probably don't want to send packet on every frame. That could easily flood the connection. Try to send packets somewhere around 10-15 times per second, i.e. every 6th frame or so.

Second of all, it seems like you've slightly misunderstood the authoritative server model. The input that the client is sending to the server is what that client is doing at the moment, so the server doesn't rewind and replay, it just applies the input. It is when the server sends the state of that client back to the client, along with the sequence number of the latest received input, that the client rewinds back to that state and applies any input that has been buffered up to that point. That way the state of the game on the server is always correct, but the interpretation of the client may vary.

Example:

Client A starts buffering input on frame 0. On frame 6 he sends 6 frames worth of input to the Server, along with the sequence number 1.

On frame 12 the Server receives the input an applies it to the corresponding character.

On the same frame the Client sends 6 frames of input along with the sequence number 2.

On frame 18 the Server sends the state of the character back to the Client, along with the sequence number 1.

On the same frame the Client sends 6 frames of input along with the sequence number 3.

On frame 24 the Client receives the state of the character along with the sequence number 1.

The client rewinds back to that state and discards any input before sequence number 1.

Since the client has buffered input with sequence number 2 and 3, it applies this to the current state, bringing him back to where he should be.

This is really just a way for the client to prematurely predict the state of the world, so it doesn't have to wait for the roundtrip before acting upon input, thus reducing input latency.

The second question is the same problem as magic bullets. Since you predict the state of the world on the client, you might trick the player into thinking that he is safe, when in fact he isn't. I can't think of any way to mitigate this.

Hey thanks so much for your reply.

I think i am getting confused between a few concepts, that's true. I've been reading so much lately! But also i am trying to achieve something slightly more with my design. I am trying to get the server to simulate every clients input for "sequence 1" at the same time. Imagine in your example scenario the server on frame 24 receives input from Client A @ sequence 3 and Client B @ sequence 1. The way you describe it these would be executed at the same time on the server. Tough luck for client B.

I was thinking of buffering input on the server side so that the slowest client has a chance to get its input sent. Then once the buffer is sufficiently full of inputs it can start simulating everyone's "sequence 1" at the same time and continue with a smooth simulation.

But now i am thinking that maybe this unnecessary, adding latency for the faster connections. I just don't know.

In general, if you structure your messaging as "requests" that need "responses," you're unlikely to get a robust networked simulation.
Each endpoint (clients, server) should send "updates" to the other end. "Updates" should contain all the information needed.
Clients already know what the server needs. Server already knows what the client needs.

Also, what platforms are you targeting?
For PC/Mac/Linux, cheating is rampant, so you really only can send "player input" from the client to the server.
For mobile phones, the platforms are slightly more locked down (at least iOS) and thus you may get away with sending "player actor state" instead.
For consoles, the hardware vendors work very hard on preventing cheating, so many console games get away with each client "owning/simulating" its own actor, and sending updates about it to the others, often echoed through one playerserver.

Now, exactly how you deal with time stamps -- do you display things in the "future" or "past" on each machine (client / server / observer); do you simulate in lockstep or opportunistically; do you guess-and-patch-up or display-known-good? All of these vary based on the exact feel you want from your game. Different choices will give different amounts of local latency, remote latency, perceived latency, rules-bending ability, number of corrections, possibility of catastrophic simulation failure, etc. We can't choose for you!

On these forums, as well as on the web, there's been a few discussions on how Awesomenauts solves multiplayer. That is a high-action multiplayer platformer, so you probably could get some insights into one particular solution by tracking those down.