Thursday, March 25, 2010
There are basically 3 timing models.
- Synchronous
- Asynchronous
- Partial Synchronous
Synchronous
Where we know the upper bound for communication time, computation time and the time difference for the physical clock. Which means we know the upper bound of response for a process.Asynchronous
Where we do not have any idea of time bound and we can not make any assumption about time.Partial Synchronous
When we assume that after some finite time the system becomes synchronous.Now let us consider different timing models on the failure detectors. For any failure detector completeness property can be satisfied by any timing model as it is a liveness property and can be satisfied in later execution.
So the property to worry about is the accuracy property. For details see here.Strong Accuracy
Can only be satisfied in synchronous system. Because strong accuracy does not allow to detect a correct node as failed even once. To check if a node is alive we use heartbeat technique. Which introduces a timeout to check the pulse to determine the node failure. In synchronous model we can specify a time out and be happy with it, because we know the time bound of the system. But for asynchronous system we do not have any time bound and can not assume anything about time. So any kind of timeout is meaningless in asynchronous model.
So strong accuracy(Perfect failure detector) is only achievable by synchronous system.Eventual Strong Accuracy
Well it is same as strong accuracy only that it is given a some finite time to get strong accurate. So it is implementable in partial synchronous model. As partial synchronous gets synchronous eventually.Weak Accuracy
weak accuracy says that at least one correct node will not be suspected by other correct nodes. That weakens strong accuracy by reducing the number of correct nodes that are not suspected. But never the less we have to ensure accuracy for one node which does not allows us to reduce our timing model to less then synchronous model. At least there should be one node with every one is well connected. And for those links the timing synchrony holds.Eventual Weak Accuracy
Then it turns out that the timing model of Eventual weak Accuracy will be same as Eventual Strong Accuracy.Monday, March 22, 2010
Failure detection is essential for many algorithms. And any failure detector is composed of two basic properties.
Actually the weak and the strong completeness is equivalent. Because given a weak completeness we can achieve strong completeness. As some correct nodes has the information about all crashed nodes it can disseminate[using BEB, and as the some nodes are correct so all the correct nodes will get the information] the list of crashed nodes and every one will be aware of the crashed nodes.
So now this property becomes liveness property because if a correct node is suspected now then there is still a possibility that in future execution no correct node will be detected as failed.
- Completeness
- Accuracy
- Strong completeness
- weak completeness
Strong completeness
Every crashed node is eventually detected by all correct nodes.
Weak completeness
Every crashed node is eventually detected by some correct nodes.
Actually the weak and the strong completeness is equivalent. Because given a weak completeness we can achieve strong completeness. As some correct nodes has the information about all crashed nodes it can disseminate[using BEB, and as the some nodes are correct so all the correct nodes will get the information] the list of crashed nodes and every one will be aware of the crashed nodes.
Correctness is a liveness property. It can be proved as if some node do not detect the crashed node yet then there is possibility that it will be detected at some point is the future :)
Now let's talk about the accuracy property. It can be classified into 4 as,
- Strong accuracy
- Eventual Strong accuracy
- weak accuracy
- Eventual weak accuracy
Strong accuracy
No correct node is ever suspected.This is really a strong property and this is safety property as well. Because if you detect a correct node as failed then the property is violated for any execution after that.
Eventual Strong accuracy
Eventually no correct node is suspected.So now this property becomes liveness property because if a correct node is suspected now then there is still a possibility that in future execution no correct node will be detected as failed.
Weak accuracy
There exists a correct node which is never suspected by any node.
So this is a safety property because if none of the node is recognized as correct node then the property can not be satisfied in any future execution.
Eventual Weak accuracy
Eventually there exists a correct node which is never suspected by any node. And this is a liveness property.So any failure detector is a combination of completeness property and any of the accuracy properties.
So here are the possible failure detectors(considering that strong and weak completeness is equivalent)
Accuracy/Completeness | Strong |
Strong | Perfect Failure Detector |
Eventually Strong | Eventual Perfect Failure Detector |
Weak | Strong Failure Detector |
Eventually Weak | Eventual Strong Failure Detector |
References
Friday, February 19, 2010
Reliable broadcast is a necessary component for many distributed algorithm. For client server architecture we are lucky that there is TCP :) to support reliable message delivery, which handles packet loss, packet retransmission, duplicate messages etc. But unfortunately distributed architecture is much complex then that, where we have multiple recipients and our target is to scale as the recipients grow.
Pros
Pros
There are lots of ways to broadcast messages. Each provides some property and cost so that we can pick according to our need.
We can classify reliable broadcast in many categories(in general),
- Best-effort broadcast
- Reliable broadcast
- Uniform reliable broadcast
- Lazy reliable broadcast
- Eager reliable broadcast
- Causal reliable broadcast
Best-effort broadcast (BEB)
Properties
BEB1: Validity | If a correct process pi broadcasts a message m, then pi eventually delivers m |
BEB2: No duplication | No duplicate message is delivered |
BEB3: No creation | No message delivered unless broadcast |
Pros
- Simpler implementation
- Works if only sender is reliable
Cons
- Sender centric algorithm, so it is not scalable
- Does not work if sender crashes
Implementation
Send the message to all the nodes using perfect channel. Perfect channel takes care of the Best-effort-Validity.
Reliable broadcast (RB)
Property
RB1: Validity | BEB1 |
RB2: No duplication | BEB2 |
RB3: No creation | BEB3 |
RB4: Agreement | If a message m is delivered by some correct process pi, then m is eventually delivered by every correct process pj |
Pros
- Carries all pros from BEB
- Provides atomicity(either all or none of the correct node delivers)
Cons
- Carries all pros from BEB
Uniform Reliable broadcast (URB)
Property
URB1: Validity | BEB1 |
URB2: No duplication | BEB2 |
URB3: No creation | BEB3 |
URB4: Agreement | If a message m is delivered by any process pi, then m is eventually delivered by every correct process pj |
Lazy Reliable Broadcast
Requires: Perfect failure detector
Property
The is a non zero probability if the sender and receiver is correct then eventually the receiver will receive the message.
Basic idea
If any node detects that the sender has crashed then RB deliver a copy of the message to all node.
Eager Reliable Broadcast
Property
Same as Lazy Reliable Broadcast. But it does not use any failure detector. It work is fail silent model
Basic idea
It does not wait for node to crash and does the RB deliver to all node.
Causal reliable broadcast
Till now we did not consider order of the messages. But if the broadcast messages are related and has a order such that m1 precedes m2 then,Properties
- if m1 and m2 is broadcasted from the same process then m1 broadcasted before m2
- if m1 is delivered by process p then p broadcasted m2 after delivering m1
- the precedence is transitive, so if m1 precedes m' and m' precedes m2 then m1 precedes m2
References
- Introduction to Reliable Distributed Programming by Rachid Guerraoui and Luís Rodrigues
- Slides from the lectures of Professor Seif Haridi, SCS/ICT/KTH.
Friday, February 12, 2010
In a distributed system a node can fail/crash in a lot of way and it is very important that we understand which failure model we are supporting while defining an algorithm. Because execution of an algorithm can change depending on the failure model.
Failure model
A node can fail in four way.
- Crash Stop
- Omissions
- Crash Recovery
- Byzantine / Arbitrary
The properties of each failure model is following,
Crash Stop
- Node stop doing anything(sending/receiving/processing)
- Once fail never recover
Omissions
It can be of 2 type as,
- Sending omission - not sending data where node is suppose to send according to algorithm
- Receiving omission - not receiving data when other node has sent message
Omission is actually a temporary state which eventually turns to a crash or a crash recovery state. Because it may recover from that state which will make it crash recovery and if it do not recovers then it becomes a crash stop.
Crash Recovery
- A node might crash
- It recovers after crashing and initiates a recovery process
Some crash recovery model also has stable storage. Nodes store state information in the stable storage and it can retrieves necessary information while it is in recovery state.
Byzantine / Arbitrary
A node may behave arbitrary (sending/receiving messages that are not specified by algorithm). This can be a malicious attack to the system.Fault tolerance hierarchy
There is a hierarchy in the crash models. Like crash is a special type of omission, where the process never recovers. Omission is an intermediate state for crash recovery, where process runs it's recovery procedure and eventually recovers from the omission state.
And crash recovery can be a special case of byzantine failure since it allows any kind of deviation from the regular algorithm. So any kind of crash can be a special case of byzantine failure.
Figure: Fault tolerance hierarchy
References
- Introduction to Reliable Distributed Programming by Rachid Guerraoui and Luís Rodrigues
- Slides from the lectures of Professor Seif Haridi, SCS/ICT/KTH.
Friday, February 5, 2010
Distributed approach for solving problem is an emerging and hot topic now a days. It is really a powerful solution. But we should all know first what is the strength and weakness of this approach before we consider of choosing this.
Disadvantage
Well in short the disadvantage of this approach is that it is fairly complex and thus costly for development and maintenance. Skilled people are needed for this kind of solution development.
Then where should we use it
In general there are 2 kind of situation where distributed approach is proffered.
- Some solutions are only possible by using distributed solution
- Some solutions are inherently has characteristic of distributed solution
Let us think about skype. Skype does not use traditional client server model rather it uses peer to peer model. This is why it can provide scalability without using costly centralized client server structure.
Subscribe to:
Posts (Atom)