|
 Sunday, May 12, 2013 |
 Where did the term 'Byzantine' in Byzantine Failure originate? Why not something else?" The term comes from the Byzantine Generals Problem. This is a generalization of the Two Army Problem. See my previous post. The Byzantine Generals are a metaphor for nodes of a distributed system.
The Byzantine Generals are introduced in a research paper by Leslie Lamport, Robert Shostak, and Marshall Pease (1982), The Byzantine Generals Problems. In this paper the authors imagine an encampment of a large enemy army. Surrounding this encampment are the Byzantine Generals. Each general commands a small brigade of soldiers. Individually the Generals would lose to the enemy, but united they win. The objective is for the Byzantine Generals to mount a coordinated attack. Unfortunately, things are gummed up a bit. Purportedly the Byzantine army had significant treachery in its high ranks. A general may be malicious and working for the other side. This would be considered a "Byzantine Failure" of a node in this distributed system. The objective then becomes for the system as a whole to act in concert in the presence of these Byzantine Failures.
A general solution to this problem can be quite difficult. Consider for example a malicious general tells half of the other generals to attack, and the other half to retreat. What protocol can healthy nodes use to maintain agreement? What if there are more than 1 malicious general in the system acting in concert? Given we have an algorithm that maintains 'interactive consistency' what is the maximum number of malicious generals that the distributed system can tolerate? Interactive consistency loosely means that all non-malicious generals (healthy nodes) always agree.
|
damon at 6:28 PM |
(2) Comments |
Add a comment |
Permalink
|
|
|
|
Tuesday, April 30, 2013 |
| What is a Byzantine Failure? |
|
 A while back, I came across the term “Byzantine Failure.” Trying to understand the term lead me on an interesting path into Byzantine networks. As an engineer or software designer part of the mission in developing new products is to anticipate the failure of parts of our system. In aerospace systems, this requirement is more formal. The customer will require an FEMA analysis. This is a thorough analysis of those parts of a system that can fail, how they can fail, why they might fail, and what you are going to do about it. One common type of failure we all might be familiar with is the crash. If part of a system were to crash, perhaps the operating computers would always read a 0 from the crashed component. A design might deal with this problem by reading some value that is guaranteed to always be a 1. If a 0 were read then we know the component crashed and something should be done about it; use a default value, alert the pilot, use the auxiliary sensors array, whatever.
A Byzantine Failure is a very high level of failure to design to. For many real systems designing to this high a level may not be practical or make sense from an applications point of view. Many aerospace systems though have a requirement for a very high level of reliability and designing a system to this type of failure can make the FEMA analysis simpler.
With a Byzantine Failure anything is possible. In the literature, the term ‘malicious intelligence’ often pops up.
A component capable of a Byzantine failure may operate normally except in that 1 case where it’s critical it function correctly. In that 1 case it may send just the wrong value to make the system as a whole fail. To make matters worse, if we are considering multiple parts of the system capable of Byzantine failure, we would need to consider the possibility that those multiple parts are working together to cause a system wide failure. We need to consider that they work in concert to do exactly the WRONG thing at the RIGHT time!
This is a very high level of error analysis to design to. However, if you do you will have taken a big step in system reliability.
|
damon at 3:28 AM |
(2) Comments |
Add a comment |
Permalink
|
|
|
|
Monday, January 21, 2013 |
| Nova University GSCIS Winter 2013 Poster Session |
|
|
|
|
Sunday, December 09, 2012 |
In my last post I gave a proposal to hardware accelerate the B+ tree. I want to discuss the search time further. The depth of the B tree is given by the fanout. The number of nodes needed to retrieve from secondary storage is given by logdn where d is the fanout and n is the total number of keys to search. This is true for both the B+ tree and the BCAM accelerated B+ tree.
Once the nodes are brought into main memory they need to be searched. Knuth proposed a linear search (O(n) search time) for small nodes and a binary search (O(log2n) search time) for larger nodes as being most efficient. With the BCAM accelerated approach we search these nodes with either a BCAM (internal nodes) or standard CAM (leaf nodes). This search time is O(1). That means the search time is a constant and independant of the size of the node.
Secondly, I got hold of the original Boeing paper by Bayer and McCreight. I was curious as to the orgin of the "B" in B-tree. There does not seem to be any light shed on this mystery. It could stand for Boeing, Bayer or Balanced. Or perhaps all three!
|
damon at 2:12 PM |
(2) Comments |
Add a comment |
Permalink
|
|
|
|
Monday, December 03, 2012 |
| Reconfigurable Hardware for Database Application |
|
Reconfigurable Hardware can provide some really impressive software performance. It does require the software to be decomposed into parallel algorithms. I devised a method of performing searches for large databases in O(1) time using reconfigurable hardware. Here is my paper on this. |
damon at 7:24 AM |
(2) Comments |
Add a comment |
Permalink
|
|
|
|
Sunday, September 09, 2012 |
| The Exponential Filter Structure |
|
[edit 10/2/12, changed to log plots]
In the last lab note we looked at the boxcar filter structure. That was an example of an FIR filter. The exponential filter is an IIR filter. In a simple implementation of this filter we calculate the filter output by taking the current sample, adding it to the previous output then dividing by 2. Mathematically y=½(x+yz-1). Since the output is a function of the previous output this is an Infinite Impulse Response filter, or IIR filter.
One of the concerns about IIR filters is that an impulse or perturbation on the input will ring forever on the output. This may be true if we are talking about real math. In a typical embedded system we work with a fixed point math. Notice that in our equation the impulse is cut in half each sample time. So for instance, our samples may be from a 12 bit A/D converter. After 12 sample times our impulse gets cut in half 12 times and then would disappear. In this case it will not ring forever. On the other hand a fixed point math can cause other issues on filters with more interesting pole/zero placement, but we are good here.
For the above function H(z) = Y/X = 1/(2-z-1).= z/(2z-1) There is a zero at 0 and a single pole at z=1/2. This is within the unit circle, thus the filter is stable. To plot the frequency response we set z=ejωT . Then we normalize by setting T=1. We can use Wolfram Alpha to plot the equation H(ω) = 1/(2-e-jω). And I copied the plot here for convenience.
Here the horizontal axis is in Hz. This filter is down to 0.7 at a frequency of 0.14Hz (remember this equation is normalized to a sampling frequency of 1 Hz).
If this is too much filtering, or too little filtering you can try adjusting the weighting of the two terms in the exponential filter. For instance, what if you choose the weighting y = ¼ (3x + yz-2)? Here I tried to use a mod 2 divisor to make the math dead nuts simple to implement on a fixed point processor. On an FPGA you would not even need to divide or shift, just pick off the right bits!! All we need is two 'add' operations. Can you calculate the frequency domain function and plot it?
If you have any other common filter topologies, leave a comment for future discussion. |
damon at 6:50 AM |
(3) Comments |
Add a comment |
Permalink
|
|
|
|
Wednesday, September 05, 2012 |
In embedded systems it is quite common to need a little bit of filtering on analog quantities. Programmers sometimes feel they need the filtering to help smooth any analog conversion noise. Two type of filters commonly used are the Boxcar and the Exponential filter. Both are simple to implement. Its important to understand the impact these filters have on delay and frequency response, and to evaluate their comparative effectivness.
The Boxcar filter is a simple averaging filter. Technically it is an FIR filter. Typically you would obtain your next analog value, add it to the last n-1 values read, then divide by n. It's just a simple average of the last few values read.
A common value for n is 4. The Z transform of a filter with n=4 is H(z) = ¼ (z3+z2+z+1)/(z3) . There are three poles at the origin in the Z domain. Thus this filter is stable. There is one real zero at -1, and two complex conjugate zero's at +i and -i. The (normalized) frequency response is given by H(ejω) = magnitude(¼ + ¼e-jω+ ¼e-j2ω+¼e-j3ω). We can use Wolfram-Alpha to plot this function. Click on this link provided and you will be whisked away to see the low pass filter response as fast as damon4.com can take you. In the following image (copied from Wolfram) we see several cycles of normalized frequency response including aliasing above half the sample rate. The aliasing is the mirror image above 0.5 Hz.
Note that the horizontal axis is in Hz. The sampling frequency ia 1Hz. One half the sample rate ia 0.5Hz - the Nyquist rate). What you are seeing above 0.5Hz is aliasing. How UGLY!
Lets try to plot the response for n=2. With this filter all we do is add the current and previous samples and divide by 2. The characteristic equation is Y = ½(X + Xz-1) .& The transfer function is H(z) = ½(1+z-1) = ½(1+z)/z . This has a single pole at 0 and a zero at -1. Thus its stable. The normalized frequency domain function H(ejω) = ½(1+e-jω). Its normalized for a sample time of 1sec. The plot looks like this.
This looks more well behaved!
Note that the horizontal axis this time is in Hz. Since the sample time is a normalized 1second, then the sample frequency is 1.0 Hz, and the Nyquist frequency is 0.5 Hz.
In my next Laboratory Note we will look at the Exponential Filter. This is actually my favorite and I will show you why! |
damon at 7:09 PM |
(3) Comments |
Add a comment |
Permalink
|
|
|
|
Wednesday, August 29, 2012 |
| Interesting, from an AP news article:
Time Warner Cable Inc. (NYSE:TWC): Time Warner Cable (NYSE:TWC) will increase Internet speeds for businesses in four New York City boroughs by up to 20 times, according to Bloomberg. The news service suggests that the move by the cable company comes in response to Google’s (NASDAQ:GOOG) Google Fiber initiative in Kansas City. The shares traded up $0.40 (0.45%) recently at $90.27. |
damon at 6:03 AM |
(1) Comments |
Add a comment |
Permalink
|
|
|
|
Tuesday, August 21, 2012 |
An engineer and a politician were arguing about whose profession was the older. The engineer said, "In the book of Genesis, it states that God created the order of the heavens and the earth from out of the chaos. This was the first and certainly the most spectacular application of engineering. Therefore, engineering is the oldest profession." The politician leaned back, smiled confidently and said, "Ah, but who do you think created the chaos?"
Actually I think that creating chaos is underrated. Engineers typically design for an 'optimal' solution. Sometime the optimal found is only a local minima or maxima. Shaking thimgs up once in a while might be a good thing (unless yours is the thing getting shaken!!) |
damon at 5:58 AM |
(3) Comments |
Add a comment |
Permalink
|
|
|
|
Monday, August 20, 2012 |
I am reading a paper, "Anatomy of a Database System", by Michael Hellerstein and Joseph Stonebraker. Its more of the nuts and bolts of Database architecture and research directions. It has a couple of interesting statistics that should be a consideration to any system architecture.
"Sequential access to disk blocks is between 10 and 100 times faster than random access. This gap is increasing quickly. Disk density – and hence sequential bandwidth – improves following Moore’s Law, doubling every 18 months. Disk arm movement is improving at a much slower rate."
Second,
"Memory copies are becoming a dominant bottleneck in computer architectures: this is due to the gap in performance evolution between raw CPU cycles per second (which follows Moore’s law) and RAM access speed (which trails Moore’s law significantly)."
This remark was directed at inadvertent double or triple buffering done by the application and then again by the OS. |
damon at 5:48 PM |
(2) Comments |
Add a comment |
Permalink
|
|
|
|