In the previous post we discussed the conservative approach to handling event queues together with the refinements or extensions. By conservative we meant that we handled only events that are safe. Safe events are those that have a timestamp greater than the current time.
In todays post, we discuss the optimistic approach that doesn't require that condition to be met. The processes simulate their queue with the hope that events with an earlier time stamp will not arrive . If an event with an earlier timestamp does arrive, the process must undo part of the simulation. This going back in time is called time warp and the events that arrive with an earlier time stamp is called a straggler. The optimistic algorithms deal with stragglers.
To address the straggler that arrives with a timestamp t, the process records the last valid state before time t. The process then rolls back to this last valid state.
However, events may have been sent to other processes after time t. These events must be undone as well. So the process can send a so called anti event to these other processes. This anti-event cancels the corresponding event.
The anti-event could arrive in two different ways. It could arrive with a time-stamp greater than the current local time. In such a case, the corresponding event has not been processed. So the cancelation action simply removes the corresponding event from the queue.
The second case is when the anti-event arrives with a timestamp less than the current time. The anti-event is itself a straggler now. To handle this straggler, more anti-events may need to be fired. In such a case, there is a cascading anti-events. How do we know that it does not continue indefinitely ? We use the concept of a global virtual time. This is the minimum time stamp in the system. There are two advantages now.
The algorithm never rolls back to before GVT.
The event scheduled at time GVT can be executed without causing a rollback.
In the approach we discussed so far, we need not roll back all actions. As an optimization, we could skip the roll back on actions that would happen regardless. If a process proceeded optimistically on an assumption that later turned out to be false, it maybe that the events were scheduled to happen regardless. So a lazy cancellation is introduced. After a process rolls back, it resumes the simulation without sending anti-events. An anti-event is sent only when the optimistic solution generated an event that is not generated by the new simulation.

Today we will continue our discussion on the DES and see if we can consider each source and server to be a separate process. Clients are passed as messages between the processes. We assume a queue for transit so that the messages appear sequentially.
Now since every process maintains a single queue for event, it has to decide when to process it. If it processed it rightaway, there might be another message from another source that should have been processed earlier. So the server has to wait for the incoming messages on all its inbound channels before deciding which one to execute. It must wait. But this could lead to a deadlock because two process could be waiting on each others inbound channel.In order to advance, we must ensure that such events arrive.
One solution is to send update events called null events. They don't do anything other than to break the impass and ensure progress. But even the null events need to be time-stamped properly.
Since null events don't take any time to process,  they don't advance the clock. For each process in the cycle, the empty queue should contain the minimum time, but this is deadlock. So a null event has to be timestamped strictly larger than the one at the current process. This null event is then sent out to all processes.
The null events break the impass because they represent a guarantee that no events will arrive earlier than this event. The increment of the null message timestamp above the current time is represented by the lookahead.
Several refinements of this basic algorithm are available. Some of these are :
1) pre-compute service time. If the service time is independent of the particulars client, the length of the time required for the next service request can be calculated before the next event has arrived. and this is typically larger than the original look-aheads.
2) Request time-updates explicitly - Rather than sending null events, processes can explicitly request null events. This occurs when a queue for a particular in-neighbor becomes empty.
3) Allow deadlock - Yet another approach is to not use null messages at all. Instead a deadlock detection scheme is used.
4) Increased synchronization -  A tighter synchronization between processes can be used to ensure that no processes get too far ahead of any other. A safety window is maintained.
All of these variants behave differently and often some experimentation is involved. Generally speaking, the magnitude of the look-ahead affects performance and this is highly application specific.

In the time driven simulation approach we mentioned earlier,  how to "discretize" continuous state changes. The simulation is advanced by small increments in physical time. This time interval must be chosen carefully because if its too large, it will not detect the events of interest and if it is too small, it will make the simulation very slow.
Together with the overall amount of physical time being simulated, the time granularity adds to the computational complexity of the simulation. Hence both the factors deserve attention so that we can simulate just what we want.
In a true DES, the absolute sizes of the time intervals between events do not affect how quickly the simulation can proceed. Only the number of events matter.
In the event queue example we mentioned earlier, we use an arrival event to seed the queue. The arrrival queue contained a single event with the description as arrival c1 and timestamp 1 represented as <arrival c1, 1>. This event is now dequeued, the "current time" is updated to 1 and simulated. Simulating this event sends the first client to the server, where there is no wait. The only time taken is the time to service the client. So the client begins service immediately.
This immediately schedules a future event to be scheduled: the completion of service of c1 at this server. This event is represented as say <complete c1, 10>.
When that event occurs, a second event is generated : The arrival of the next client. Say this event is <arrival c2, 4>. Now both the events are inserted into the now empty event queue in the increasing order of time.
Thus we set up a loop for events to be processed at this queue. Note that we keep track of the timestamps only, so from our earlier discussion, this is local. When we want to capture the state across different systems we use snapshots.
Notice that the events are queued in a single queue. To alleviate the bottleneck, we could have a few more queues depending on how many the processor can handle. Typically one more queue per processor could help.
If the processor would like to keep track of the priority of the clients, then that could be maintained as separate queues for priority or another data structure.
In the parallelized case, we still honor the arrival events and mark with appropriate time stamps.
This is how DES systems do time based simulation. 

Discrete Event simulation
This is yet another interesting topic in distributed computing. Consider a network of nodes and directed links between the nodes. There are three categories of nodes. source servers and sinks.
Source generates clients that travel through this network along the links. The clients get service at the server node. Servers can provide service to at most a single client at a time. Clients are in a queue at the server. Finally, the clients disappear at the sink.
The behavior of the system over time can be defined as a series of discrete events over time.
There are four different kinds of events:
A client arrives in the system
A client arrives at a server
A client completes service
A client leaves the system
With a precise event, we can assume no two events happen at the same time.
DES is therefore characterized by a list of time-stamped events described above that occur in increasing order of time. One use for this list is that we can gather metrics  such as average queue length etc.
These systems can be simulated to gather the relevant measurements and statistics. System can then be tuned to optimize performance.
Events are generally not affected in their service by previous clients at the same server. Therefore clients are independent.
The data structure used in DES is an event queue. This queue maintains a list of scheduled future events in increasing order of time. Simulating an event from this queue could generate new events that are inserted into the event queue.
Clients are generated at the source using an initial arrival event. Now simulating this arrival event involves both the insertion of new clients and the scheduling the next arrival.
One limitation with the approach mentioned here is that we have a single event queue that can be a bottleneck. Since events have to wait for earlier events to be simulated, one way to remove this bottleneck would be to parallelize the events.
There are also other simulations such as time driven simulations. In discrete event simulation, the absolute sizes of the time intervals between events does not affect how quickly the simulation can proceed. Only the number of events matter.
For continuous systems, this is not suitable. For example, take the cueing of billiard balls or when they collide. If we discretize the state changes we cannot predict the next event. So we have to take finer time slices.
In general, the computational complexity is proportional to the amount of physical time being simulated and the granularity of the time steps.

In the previous post, we discussed synchronous network with faults. In today's post, we will continue the discussion and look at specific faults/ One specific failure is called the Byzantine fault. Here two processes must agree but their messages may get lost in transit. If there were n rounds of messages, each could have a failure so the processes may each start out with a binary value and at the end of each round, may still have opposing binary values. Consequently, there is no convergence as the rounds decrease from n to 1.  Such faults are generally more difficult to tolerate than crash faults because the outcome is to simply stop execution . There is no solution when there are three processes.
Authenticated messages alleviate this problem. Because now the processes can now that the message was signed by the sender and no one else. This message is also tamper proof and the receiver can know that this was the intended message by the sender.
Now the same can be used to address the Byzantine fault with just two rounds. The signed messages are compared and the proposed value is discarded if the same value was not proposed to all the parties.
So each process takes the following steps:
1) broadcast signed value to all other processes
2) broadcast set of received (signed) values
3) compare received values for each of the other processes
4) if they agree, include the process that sent the value, else exclude it
5) choose minimum value of the included process
As compared to the crash failure where the fault could occur in the first or second round, in this fault the faulty process continues to execute so that there may be faulty messages in both rounds. And after the second round, the processes know that whether any faulty message was sent in the first round regardless of any faulty messages in the second round.
This problem becomes more interesting when there are more than one processes that can fail. In this case, rounds don't suffice. Instead a consensus tree is constructed.  In this tree, the nodes at level i represent message chains of length i. The message at depth 3 has signed messages contained one within the other from three processes. The root has n children representing the messages received in the broadcast of the first round. Each of those nodes have N-1 children from the messages received in the second round and  each of those nodes have N-2 children from the messages received in the third round and so on.
At a given level say N-3 the messages look like (l,k,j,1), (l,k,j,2), (l,k,j,3)...(l,k,j,N). In this case, Pj relayed the same message regarding Pk which in turn relayed Pl to all the processes. So the messages all agree. The decision value of these children can then be bubbled up to the parent.
In order for this tree to calculate the same value for all processes, every message chain in the leaf nodes must include at least one non-faulty process. Thus in order to tolerate f faults, the leaf nodes must represent message chains of length f + 1. That is a consensus tree of height f+1 is required.
The consensus tree also helps in cases when the authenticated signatures are not available. In this case, the value from the children will be bubbled up to the parent only when a majority is there. This is based on the assumption that the majority will be non-faulty and so a quorum suffices and the correct value will be bubbled up.

Asynchronous consensus with process failures.
When there is one fault, it is impossible to solve the consensus problem in a distributed system that involves asynchronous model. Unfortunately, asynchronous design is common. Faults also happen such as failures of disk. And it only takes one fault to disrupt consensus.
This has been proved based on the observation that a protocol begins in a decision state value is either 0 or 1. And it continues in which either result is still possible.
In transaction systems, for commit/abort we used the two-phase locking semantics. In group membership, leader election and reliable multicast too , this problem is common Hence, some suggestions to modify the assumptions of the problem include:
1) Synchrony - If a system can provide an upper bound on the delay or recovery, then this problem can be solved.
2) Randomness - Some probabilistic algorithms can help
3) Failure Detectors - a delayed process is difficult to differentiate from a crashed process without a failure detector.
4) Approximation - Even if all the process cannot agree on the same value, some arbitrary value can suffice.
Let us look at synchronous agreement with process failures.
Every process broadcasts to all other processes its initial value and this can be done in a single round of messages. All of them can then agree on say the minimum.
If there were to be a crash before the first round completes, then they may not have all the values. So a second round of messages could be initiated with all the values from the first round so that everyone has the same set.
Notice that if there are more failures, then there must be more rounds before the agreement. In such a case, there must be an upper bound on the number of rounds otherwise this may not converge.
Also there could be authentication and encryption involved in the messages so that it is not tampered  and that it can be shared effectively. We don't focus on those at this time because we are addressing a different issue.
When we discussed the solution for synchronous systems, we may see how the assumption modifications come useful for asynchronous networks.

We will continue our discussion on garbage collection. The process has some steps that are not obvious. We will go over them in this post.
First, we look at the propagator step we added.  The propagator tests a condition for each edge. This condition marks an edge between x and y as ok if x is a root and with an edge between x and y, they are connected with y as root. That is the propagator takes each garbage and connects them to food.  It continues execution until a termination condition has been reached where the root is connected with all the vertices visited such that each edge x,y is ok.
Between two edges there is only one condition when the edge is not ok. This is when x is not a root. If x is not a root, it is manure. A manure is now easy to collect.
The fact that x is manure and is not a root is maintained as an invariant with the progress because we add edges. Notice that in the ok condition, we checked and maintained that y is root. This is a refinement from the earlier definition where we considered y is food. This let us come up with two separate connected graph where one is manure and the other is food. Everything else is unconnected and garbage.
To be able to prove that this is the case, we considered our actions and maintain the invariant that if x is manure it is not a root. Said differently, each vertex is neither manure or not a root for the marker to propagate. We show that this invariant holds throughout the progress.
Initially there is a root for food and  manure is part of garbage. This is easy to establish because the food is mutually exclusive. By definition, food is any vertex that is reachable to the root. So our initial condition holds.
Next in our actions, we look at the two that change a vertex from being or not being a root.
The first is when we add the edge between x and y  and y is food. In this case since y is food, it is not manure. Since the initial invariant holds for all vertex that is not y, adding an edge from that vertex to y, maintains the invariant.
The other action we do is when x is a root and now there exists an edge between x and y. In this case we proceed from the left. If x is not manure and we connect y, then y is not manure. if y is not manure, then y is root. This re-establishes our invariant.
Thus by maintaining our invariant and our progress, we are able to propagate. we detect the termination condition when the root is chosen and all the edges reaching to it are ok.