Case by case explanation of the CAP theorem

You know the saying: “You can have it done fast, cheap or right; choose two”. This is something no boss or customer wants to hear, but it is also very true. It is like a law of nature. You cannot talk your way around it. You cannot outsmart it.

My opinion is that for someone to fully understand this saying, she has to examine all the cases. Fortunately, there are only three cases:

Case 1: If you do it fast and cheap, prove that it will not be right.
Case 2: If you do it fast and right, prove that it will not be cheap.
Case 3: If you do it cheap and right, prove that it will not be fast.

By proving these three cases, the saying is proven in its entirety. Ok, let’s do that. (I beg your pardon?… Oh, the CAP theorem. Yes, we might get there, eventually. All right then). After this brief interruption, let’s prove all three cases of the saying.

Case 1: You do something in a manner that is fast and cheap. Fast means that you do not spend a lot of time in the design, making and testing. Thus, for the product or service to come out right, you need to have a lot of resources and employees. But you also do it in manner that is cheap, which means that you do not allocate a lot of resources and employees, because these cost. So it is impossible for the product or service to come out in a rightful manner.

Case 2: You do something in a manner that is fast and right. Since it is done fast, you have to allocate a lot of resources and employees, in order do it right. Thus, it cannot be done cheaply, because resources and employees cost. Let me give you an example. I do not like watching cars racing, but there is a lesson to be learned here. When a Formula 1 car is stopping to change tires, this is done fast and right. Have you seen how it is done? A lot of technicians with special equipment and tools rush to the car. They lift it with a special mechanism and there are dedicated technicians allocated to each and every tire. Now this could have been done more cheaply, if there was only one technician, but this would not have been fast. Or it would have been half-done.

Case 3: You do something in a manner that is cheap and right. That may mean that one employee will have to do the whole thing. And she will have to take the time to see that it is done right. So it cannot be fast.

So we have proven that the saying is correct. I love these thought experiments and proofs, don’t you?

The CAP theorem reminds me a lot about the saying. The CAP theorem sort of states that you can have a system that is Consistent, Available or Partition-tolerant, choose two. And this is difficult to understand at first. But if we examine and prove all the cases, one by one, the CAP theorem will have been reduced to an easy concept to grasp. Of course, it is obvious that we also have three cases to study here:

Case 1: If a system is consistent and available, it cannot be partition-tolerant.
Case 2: If a system is consistent and partition-tolerant, it cannot be available.
Case 3: If a system is available and partition-tolerant, it cannot be consistent.

Let’s prove these three cases by studying the simplest example there is, without any loss in generalization. Let us assume that we have two different computers on the same LAN. Each of these two computers has a local database with exactly the same schema and no data (or exactly the same data) at first. We also have a separate hardware load balancer on the LAN that makes these two computers appear as one to client applications. The client applications do not know about the two computers; they only know and contact the hardware load balancer. The hardware load balancer sends client requests to whichever of the two computers happens to be available, without any notion of history, previous requests, state etc. For example, a client application could access one server at first, then for a second request could access the other server. The hardware load balancer does not care. It will send the request to whichever server happens to be available, in a manner that will make both servers process roughly the same amount of requests, and that’s all. Each client application writes to the database and reads from the database of the server that it contacted.

So this is our system: two servers (each with its local database) and a hardware load balancer. For our system, three things are desirable: consistency, availability and partition-tolerance. Let’s define these attributes according to our system.

Consistency: Our system is considered to be consistent, when the answer that a client gets is the same, no matter which server the client contacted. That means that the local databases in both servers are synchronized (that is, contain exactly the same data). If the databases are not synchronized, the system must not answer a client’s query, because the answer will not be consistent; that means that the answer will depend on the particular server that the client request was sent to by the hardware load balancer. If the system answers a query without the databases being synchronized, the system will behave inconsistently. So, for the system to be consistent, the system has to answer queries when the databases are synchronized, and also, the system has to decline to answer queries, when the databases are not synchronized. To decline to answer queries when the databases are not synchronized is not bad for a consistency point of view. It is only bad from an availability point of view.

Availability: Our system is considered to be available, if a query gets answered, even if only one of the servers is down or the connection between the two servers is down. We do not examine the case in which both servers are down. If both servers are down, then, of course, the system will not be available, but this is not what availability means in our case. In our case, we only consider the case of at least one server being operational. You might ask why this is so. Well, when you want to augment the availability of our system, you just add more servers and more redundant connections (and more resilient load balancers). But even if nothing works and all servers are down, this does not mean that the system was not built with availability in mind. Let me give you an extreme example: If earth, or the solar system, or the universe is destroyed, our system will not work. This does not mean that our system had no availability built in. So we study availability only as the responsiveness of our system even if part of it is responsive. In our case, if only one server is up, the system should respond, otherwise we consider it to lack availability. And if one or both servers are up but they have no connectivity between them (but the client can access one or both of them), the system should respond to the client, otherwise we again consider it to lack availability. If our system declines to answer a query because it is not sure whether the two databases are synchronized, means that our system lacks availability. If our system answers a query with data that depend on the server that was used, this means that the databases were not synchronized and that our system is inconsistent, but, in this case, our system is available, nonetheless.

Partition-tolerance: This may be a new concept to some people, so it certainly needs to be defined. The way we built our system, it functions as a whole. But if, for some reason, the two servers cannot communicate with each other, the system is broken in two parts; it becomes partitioned. So, if the servers cannot communicate with each other, the system is divided in two independent, autonomous partitions (each server constitutes one these partitions). Now this partitioning can happen for a lot of reasons. The LAN connection between the servers might malfunction, there might be a network configuration or permissions problem, the software that handles the communication might exhibit a bug, etc. It does not matter what the problem is, just the result: the servers cannot communicate with each other, thus each server is unaware of the changes in the other server, so the databases cannot be synchronized. In such a case, the system can either respond and thus be inconsistent, or not respond and thus be unavailable. Also, it is important to understand that partition-tolerance is a good thing. We want (if possible) a system to be partition-tolerant, as we want it to be consistent and available. Partition-tolerance means that the system continues to operate and function correctly even when it has become partitioned, i.e. the servers cannot communicate with each other. Partition-tolerance is another phrase for “we can tolerate the servers being unable to communicate with each other; no problem”.

Now that the desired system attributes have been defined, we can analyze the three cases:

Case 1: The system is consistent and available. This means that every request is answered and it is answered with consistency. Since every request gets a consistent answer, the servers communicate with each other, in order to guarantee consistent results. Thus, the servers have their databases synchronized. Since they also answer and do not decline (the system is available), this means that a partition is not tolerated. The communication between the servers cannot be cutoff. If the servers would stop to communicate between them, then their databases would not be synchronized. In that case, the system would either have to stop responding to clients (be unavailable) or respond with unsynchronized data (be inconsistent). Thus, for the system to be both consistent and available, the servers have to be able to communicate with each other and thus, a partition of the system in two is not tolerated.

Case 2: The system is consistent and partition-tolerant. The system is consistent, which means the servers communicate with each other and keep their databases in sync, or the servers cannot communicate and the system does not respond in such an event. Since the system is partition-tolerant, we can have the servers stop communication between them. Since the servers cannot communicate with each other, they cannot synchronize their data. And since we have consistency, this means that the system will not respond to queries. The system cannot respond because the data is not synchronized and any response would be inconsistent. Since the system cannot respond to queries, the system is unavailable.

Case 3: The system is available and partition-tolerant. Since the system is partition-tolerant, the servers do not have to be able to communicate with each other, thus we can assume that their databases are not synchronized. Since the system is available, the system responds to queries. Thus, the system’s responses will be inconsistent, since each server will provide its own version of the “truth”, i.e. the data.

Since the three cases are now proven, the CAP theorem is proven in its entirety.

I wrote this blog post for three reasons. First of all, when I first learnt about the CAP theorem, it reminded me of the saying I mentioned in the beginning of the post. So I wanted to bring the saying and the CAP theorem “together” in the same blog post. Second, I wanted to explain the CAP theorem through a simple system, where I would define and explain the three desirable attributes of the system. Third, I wanted to analyze the three cases of the CAP theorem separately. I believe that the CAP theorem is hard for some people to understand, because the three attributes are not defined and explained thoroughly and the three cases are not analyzed separately.

I would also to address how the saying and the CAP theorem are used “in the wild”. From what I have seen, there are rather unfair approaches to the saying, whereas this is not the case with the CAP theorem.

Bosses and customers in general do not want to come to terms with the saying. They do not like what the saying denotes, perhaps because it is against their own selfish interests. What bosses and customers want is fast, cheap and right. All three. But this is impossible. Bosses and customers do not want to be told that something is impossible. What they really want is for something to be done fast and cheap. They also want the extra costs associated with this approach to burden the employee (if we talk about bosses) or the provider of the product or service (if we talk about customers). So this is their way of having something done fast, cheap and right. In my opinion, this way is not only unfair, it is also dumb and inconsiderate. And I am not really sure which of these three (unfair, dumb and inconsiderate) is worse.

The CAP theorem on the other hand is used in a fair manner. Actually, there is no way to misuse it. Obviously, there can be no loopholes for unfairness and inconsideration as far as the CAP theorem is concerned. So, in the “wild”, there are cases where a single database server is used and thus it contains a single version of the “truth”. But in cases where it is needed to scale out rather than up (actually, you cannot scale up indefinitely), then the CAP theorem provides a much needed guideline. A usual scenario is that of eventual consistency. Eventual consistency is all the rage, today. (You can sing the last sentence in the tune of the last sentence in Jamiroquai’s “Virtual Insanity” song: “Virtual insanity is what we’re living in”.)

What eventual consistency means is that the system is built in a way that consistency is not upheld. So, a system with eventual consistency is not consistent. Only systems in which there is immediate consistency can be described as consistent. From the CAP theorem we understand that a system with eventual consistency can be available and partition-tolerant. The term “eventual consistency” describes how the system deals with its inherent inconsistency. It is built in a way that it constantly tries to synchronize the data in all its partitions. So, all changes “eventually” reach all partitions. This is a particularly good model for a lot of applications, those that do not require perfect consistency: applications such as business intelligence, log analysis and social data analytics. Such systems (systems that do not require consistency) can scale easily, because they are available and partition-tolerant.

I would also like to express my most sincere admiration to the people who came up with the CAP theorem. They are extremely perceptive and insightful. The CAP theorem brings the matters of consistency and availability under a whole new light. Suddenly, with the CAP theorem, these matters have become crystal clear. Who knows what triggered this brilliant thinking. Let me speculate. They way I imagine it, there might have been some “wise guys” claiming their systems were both consistent and available. Although they might have been correct, they might have also thought that they had achieved perfection. So the CAP theorem discoverers set the record straight by denoting that the Achilles heel of such systems is that they are not partition-tolerant. Of course, this is pure speculation from my part. Things may have played out differently, to inspire these awesome people.

Although the saying and the CAP theorem have no conceptual correspondence with each other, in my mind they share something in common, something that I find very important. When I first found out about the saying, I thought that it would be cool if for every skill that I acquired, I would learn to do it fast-and-cheap, fast-and-right and cheap-and-right. This way I could provide the full spectrum of services when needed. I think that you truly know how to do something when you are able to do it with all three ways. The same goes for system design. I believe that you truly know how to design systems if you can design them as consistent-and-available, consistent-and-partition-tolerant and available-and-partition-tolerant, depending, of course, on the particular needs they will fulfill.

So there you have it: the CAP theorem analyzed and explained in simple terms. And I did it fast, cheap and right. All three. Oh, wait! This cannot be done! Let me go once more through my notes…

The star system makes cinema a leaky abstraction

Title: The star system makes cinema a leaky abstraction
Alternative title: Leaky abstractions in everyday life

The star system makes cinema a leaky abstraction. Actually, not only cinema, but many other forms of entertainment as well.

Let me explain.

In this blog post, I would like to write about leaky abstractions in everyday life. We have Joel Spolsky to thank for the term “leaky abstraction”. It is a great service to mankind when occurring patterns are identified and named, so we can augment our understanding. Leaky abstractions are such a pattern. The Long Tail is another example of occurring pattern. And so on. We need to bring these forth so we are aware of them and so we can study them and also study their consequences. This is paramount in order to understand the world around us.

Ok, well, leaky abstractions in every day life. Let me start. I was talking to a friend of mine, who is a driving instructor, and he was telling me…

– Insert music here that takes us back in time –

Driving instructor: It is a lot easier to teach someone how to drive, if she had a prior driving or riding experience with another vehicle.

Me: Of course. Riding a motorcycle teaches you many of the things that a car driver needs to know. You have to learn what the street signs mean, for one.

Driving instructor: Yes, but you don’t get it, yet. It is a lot easier to teach someone how to drive, if she had a prior driving or riding experience with another vehicle, even with a bicycle in her own back yard.

Me: A bicycle???!!!

Driving instructor: Yes. Riding a bicycle teaches you things like inertia. When you ride a bicycle and you hit the brakes, you learn how this works: You don’t stop immediately. There’s inertia. You don’t stop dead cold at the point at which you hit the brakes. A person that has never ridden so much as a bike may not understand that. I get this from some of my students.

Me: Gosh, you have some strange students! And, all right, I will not call you “Gosh”.

– Insert music here that brings us to the present –

After this conversation with my driving instructor friend, this brake-inertia-thing seems to me like a leaky abstraction. Unfortunately, when you hit the brakes, you are not completely covered. You have to take your speed into account in order to calculate the point at which you will eventually stop. “Eventually” is the key word here. You do not stop immediately.

Now, if you are taking a driving lesson and your instructor asks you to hit the brakes, do not start shouting “leaky abstraction, leaky abstraction!”, because your instructor might misinterpret this to mean leaky brakes or something. So, let us keep this thought between you and me.

Come to think of it, a car provides many examples of abstractions. Let us take the steering wheel for example. The steering wheel is an abstraction that is not leaky. You steer left, the car goes left. You steer right, the car goes right. Excellent!

Driving a car with automatic gear transmission also provides an example of an abstraction that is not leaky. The gears change by themselves according to the speed of the car and the driver does not need to bother with them. The driver only has to “tell” the car whether to move forward or in reverse.

But a car with manual gear transmission (with a stick) is a leaky abstraction. In fact, the manual gear transmission should be considered a textbook case of leaky abstractions. The problem is not with the stick per se, but with the clutch. To change gears, you have to step on the clutch pedal. So far, so good. But you also have to step on the clutch when you start the ignition and there is a gear on (that is, the stick is not on neutral). This is because the clutch separates, as well as unites, the engine with the wheels. When we step on the clutch, the engine and the wheels are separated. When we release the clutch, engine and wheels are united.

We also have to understand that when the engine and the wheels are connected, it is not possible for one to be active and the other to be still. Thus, to start the engine, we have to first separate the engine from the wheels by stepping on the clutch, then start the engine, and, after that, slowly release the clutch in order to slowly connect the engine with the wheels, because the connection of the running engine with the immobilized wheels has to be gradual.

So, in order to understand how to use the clutch and the stick, we have to understand the underlying mechanism of how the engine and the wheels interface. The clutch does not shield us from the underlying car mechanics. Huge leaky abstraction. Again, if you drive a car with a stick, do not go screaming “leaky abstraction, leaky abstraction!” any time a car mechanic opens the hood of your car, revealing the engine, because the mechanic might think the car leaks oil or something. Yes, let us keep that between us, too.

And now, without further ado, the moment you’ve been waiting for. I am going to address the effect the star system has on cinema and theater. In the early days of the cinema, people would go and watch a movie without any knowledge of the actors’ names. The movie would end, cinema goers would go home and that was it. But as time went by, people started caring and asking questions about who would be the actors that would appear in the movies they would go to watch. Actors that the audience found successful would stimulate movie goers more. Movie goers wanted successful actors to appear in the movies they watched. And, so, the star system began to form.

Nowadays, when people go the theater, go to watch a movie or see a movie or a series on TV, they want to know the names and lifestyle of the actors. This is a leaky abstraction. It would just suffice to understand the characters and the plot in the play or the movie. Knowing details about the actors’ lives does not lead the audience in any way to a better understanding of the plot or a better enjoyment of the performances and overall experience.

Yet, we want to know about the people that star in the movies and plays we watch. We are very interested in their names, their real life stories and their lifestyle. We are fascinated by the actors so much that we want the role playing abstraction to leak. We want it to leak badly. This is why paparazzis exist.

So, while abstractions should generally shield us from the underlying details and they should not leak, there are cases where we actually want some abstractions to leak. In some cases, we want to know the underlying details and we do not want to be shielded from them. We want to know the painter that painted a drawing, even though this will not change the actual drawing in any way. We want to know the fashion designer that designed a piece of clothing, even though it will continue to look, fit and fell the same. Some abstractions are not leak-proof and we want them this way.

Rickshaw Jam Stage 32 Walkthrough

Some of my friends had trouble with the 32nd stage of the game Rickshaw Jam. So I solved this stage and I present my solution here. My solution is completed in 37 steps. Along with the initial state (step 0), all and all my solution is presented here in 38 images.

One way that you can use the images is that you can download them in a folder and use the built-in Windows image viewer to view them, using the arrow keys. This way, it is like watching a video of the movements, with the added benefit that you can control the speed of the 38 “frames”, by the rate at which you click the arrow keys.

Location, location, location is not for cloud taxonomy

When refering to public and private clouds, people consider as public the clouds that their resources are located in the cloud hosting provider’s data center and are leased to organizations, whereas people consider private the clouds that their resources are located in the organizations themsleves.

This is the definition almost everyone seems to use for public and private clouds and is an easy concept to grasp.

But Microsoft does not like this definition. In “With System Center 2012, Microsoft Democratizes the Private Cloud” (InstantDoc ID #141927), Paul Thurrott provides the exact definition and differentiation of the two types of clouds, after speaking with Microsoft corporate VP Brad Anderson. To me, Microsoft’s point of view makes perfect sense.

For those of us who would like a more formal and accurate definition, the location of the resources must be left out of said definition.

The way I understand it, a company uses a private cloud if its workloads are running in a fabric dedicated to that company. If a company’s workloads run in a fabric shared with other companies, then the company uses a public cloud. It does not matter where the underlying hardware of the fabric resides, or who provides the fabric. All that matters is whether the hardware is dedicated to one company or serving multiple companies. The location of the hardware is irrelevant.

Closing, I would like to say that location, location, location is not for cloud characterization (hey, it rhymes, too).

Beginner’s guide to solving Rubik’s 2X2

Title: Beginner’s guide to solving Rubik’s 2X2
Alternative title: All your cube are belong to us
Note to self: All the YouTube videos that show how to make the tube spin easier by lubricating it, are doing essentially what I call “They lube the cube and tube the lube”.

And yes, you have to endure these lame (to say the least) jokes of mine in order to read this guide.

Rubik’s 2X2X2 cube (2X2 in short) is solved like Rubik’s 3X3X3 cube (3X3 in short), where in 2X2 we only have corners. In 2X2 there are no edges, so we only need the algorithms and procedures from 3X3 that pertain to corners.

In this guide, I will describe two easy methods for solving the 2X2. “Easy” means that the person who solves the cube does not have to remember a lot of cases and algorithms. So these methods are easy to learn. The downside is that they require a lot of movements. There are other methods that solve the cube using less turns, but they are not easy to memorize. These other methods are for advanced solvers. This is why I characterized this guide as a “beginner’s guide”. 

It is fundamental to understand the difference between a layer and a face. A solved layer has correct colors an all sides as well as its face, whereas a solved face may not have correct colors on the sides.

It is also fundamental to understand the difference between turning a layer and orienting the cube. When we turn a layer, the rest of the cube remains still. When we orient the cube, we rotate the whole cube without changing it.

It is also fundamental to understand that a corner can be in its correct position but not with the correct orientation. If a corner is in its correct position and with its correct orientation, then we consider this corner to be completely solved. This last concept will be used in the second method that I will describe.

I will use the standard notation for the movements that need to be done. This notation is described in the excellent and colourful PDF guide for the 3X3 in the rubiks.com web site.

For the following methods we will first solve the white layer with no help and then we will use algorithms to solve the opposite layer (the yellow layer).

First method for solving the 2X2

I learnt this method by reading the PDF guide for the 3X3. In this method, to solve the yellow layer, we first put all yellow squares at the top face and then we rearrange them in their correct positions.

First step: We solve the white layer with no help, then we orient the cube so the solved white layer is at the bottom, facing the floor. 

Second step: In this step, we will bring all yellow pieces to the top (without caring about their sides), thus creating a yellow face.
The procedure to do that is described in the PDF guide, in the page titled “SOLVE THE TOP LAYER – GET ALL THE YELLOW ON TOP – 2nd Step: Make all the corners yellow”.
I will describe the procedure here as well:
(Please note that before we begin, we do not need to turn the upper layer in relation to the bottom layer. In other words, the relative orientation of the two layers does not matter.)
Procedure for the second step:
First we look at the top face.

• If all squares are yellow, we do need to execute this procedure and we can proceed to the next step.
• If there are no yellow squares on the top face, we orient the cube so that we have a yellow square on the near-to-us left upper side square.
• If there is one yellow square on the top face, we orient the cube so that the yellow square is on the near-to-us left top square.
• If there are two yellow squares on the top face, we orient the cube so that we have a yellow square on the front left top side square.

After this orientation of the cube, we perform this algorithm: R U Ri U R U U Ri. If, after this algorithm, all top squares are yellow, we proceed to the next step. If not, we repeat the procedure.
Please note that the algorithm R U Ri U R U U Ri leaves the bottom layer intact after it is finished. Thus, during different executions of the procedure, we can turn the top layer in any way we want, although this is unnecessary. So we can orient the cube instead of turning the top layer, but either turning the top layer or orienting the cube will do.

Third step: This is the final step. In this step, we will rearrange the yellow corners so that they are in their correct positions.
The procedure to do that is described in the PDF guide, in the page titled “POSITION THE YELLOW CORNERS CORRECTLY”.
I will describe the procedure here as well:
Procedure for the third step:
First we turn the top layer so that as many corners as possible are in their correct position.

• If all four corners are in the correct positions, then the cube is solved!
• If two corners next to each other are in the correct positions, then we orient the cube so that these corners are in the back and we do the algorithm Ri F Ri B B R Fi Ri B B R R Ui. The cube is solved!
• If two diagonal corners are in their correct positions, we do not have to orient the cube in any particular way, and we do the algorithm Ri F Ri B B R Fi Ri B B R R Ui that was just mentioned. This will transform the upper layer in such a way that we will be able to turn it (the upper layer) so that two corners next to each other will be in the correct positions. So we then orient the cube so that these corners are in the back and we do the algorithm Ri F Ri B B R Fi Ri B B R R Ui one final time. The cube is solved!

This method is thoroughly described in the two pages of the PDF guide and we only have to learn two algorithms R U Ri U R U U Ri and Ri F Ri B B R Fi Ri B B R R Ui. This method requires minimum thinking and examination of the cube.

Second method for solving the 2X2

I learnt this method by watching YouTube videos, although I did not find them completely correct. Here I present my own variation of the method. In this method, to solve the yellow layer, we first put all corners in their correct position without caring if their yellow square is at the top, and then we perform an algorithm that has the end effect of rotating each corner in place to bring the yellow squares on top. So, conceptually (but not procedurally or algorithmically), we go the opposite way than the first method. (In the first method, we first put the yellow squares on top and then we put the corners in their place. In this method, we put the corners in their place first, and then we put each corner’s yellow square on top.)

First step: We solve the white layer with no help, then we orient the cube so the solved white layer is at the bottom, facing the floor.

Second step: In this step, we look at the top layer and we turn it in such a way that the maximum number of corners are in their place (but we do not care if their yellow square is on top or not). (Please note that either two of four corners will be in their correct place if we turn the top layer appropriately in relation to the bottom layer. If you find that only one corner is in the right place, continue turning the top layer until two corners are in their place. In other words, in this variation of mine, it is incorrect to continue with only one corner in the right place.)

• If four corners are in their place, we continue to the next step.
• If two corners next to each other are in the right place, then we orient the cube so the two correct corners are in the back and in order to bring all corners in their place, we perform the algorithm U R Ui Li U Ri Ui L. This algorithm is quite “symmetrical” and easy to remember once you perform it even once. After this algorithm, we turn the top layer so that all corners are in their correct place and we continue to the next step.
• If two corners diagonally are in their right place, we orient the cube so that either one of these corners is in the upper right front and we perform the algorithm U R Ui Li U Ri Ui L. This will make the top layer obtain two corners next to each other and in their right place. Next we orient the cube so the two correct corners are in the back and in order to bring all corners in their place, we perform the algorithm U R Ui Li U Ri Ui L once more. After that, we turn the top layer so that all corners are in their correct place and we continue to the next step.

Third step: In this step, we will perform a procedure that will have the end effect of rotating each corner in place to bring the yellow squares on top.
First, we examine the top layer to find if at least one corner is in the correct place and also has the yellow square on top (thus effectively a corner completely solved).

• If all corners are completely solved, then the cube is solved!
• If at least one such corner exists (if any, there will be either one or two, not three and with four we have the complete solution), we orient the cube so that any of the completely solved corners is in the upper left front and an unsolved corner is in the upper right front.
• If no completely solved corners exist, then it does not matter how we orient the cube (in other words, it does not matter which unsolved corner will be in the upper left front).

We then perform the algorithm Ri Di R D as many times as needed to get the upper right front corner completely solved. Then we turn the top layer clockwise (we do a U). If the corner that is now in the upper right front is solved, we perform a U again and continue. If it is unsolved, we again perform the Ri Di R D algorithm as many times as needed to get this upper right front corner completely solved. And so on, until all top layer corners are completely solved. Then, we might need to turn the upper layer to get it aligned with the bottom layer and then the cube will be solved!
(The procedure that we use in this last step is also demonstrated (albeit a little differently, but it does not matter) in the second part of the excellent YouTube video Rubik’s Cube Questions Once Again Answered).

For this method, again we only have to learn two algorithms: U R Ui Li U Ri Ui L and Ri Di R D. These algorithms are easier to learn than the ones in the first method. The problem with this method is that in the beginning of the second step we need to examine the cube to find and position the upper layer for the maximum number of correct in-place (but not necessarily with the yellow square facing up) corners and this may take time observing and turning and matching. Also the second algorithm (Ri Di R D) may have to be performed a lot of times in the third step, something that may be tedious.

Which method should you use?

Well, you can use any one of these two methods. Practice and decide for yourself. I prefer the first method, because it does not require a lot of thinking and examination, although the algorithms are a little bit harder to memorize (but not that much).

Actually, the best thing to do would be to decide after the first step. The first step is the same in both methods. After the first step is done, it may so happen that all yellow squares are on top. Then it may be wise to choose the first method, since its second step is already done. Or it may so happen that after the first step, two corners are completely oriented and solved and even better, the other two corners are in their correct place. Then it may be wise to choose the second method, since its second step is already done and also half of its third step.

Explanation of how I created the variation of the second method

This second method is a variation that I created (but I am sure that others have thought of it also). My variation pertains to the way I solve the second step. I began with the algorithm U R Ui Li U Ri Ui L and the knowledge that what it does is that it acts on the top layer in a way that it leaves the right front upper corner intact and rotates the other three upper corners counter-clockwise. That knowledge was enough for me to use this algorithm (and this algorithm only) to correctly position all upper corners in the second step of the method. 

When we begin the second step, it is obvious that we can choose any one of the upper corners and position it in its correct place. But if we choose and position one corner at random, chances are that the other three corners will not be in their correct positions. After all, the final goal of the second step is that: to correctly position all corners and we are in the beginning of this step.

Now please note that it is possible to turn the upper layer in such a way that not only one but two corners will be in their correct place. These corners will either be next to each other or diagonally from each other.

But let us choose to correctly position a corner that places no other corner in its correct position. In this case, we would like to orient the cube so that the correct corner is in the right front upper corner and use the algorithm U R Ui Li U Ri Ui L.

We know that the algorithm will leave the correct corner intact and we also know that it will rotate the other three corners counter-clockwise. Unfortunately, the use of this algorithm, no matter how many times we execute it, will not produce every possible orientation of the four corners and it may so happen that the orientation that it will not produce might be the desirable one.

For example, suppose that we look at the upper layer and corner number 4 is in its correct position and corners 1, 2 and 3 are not. By repeatedly applying the algorithm, we obtain the following configurations:

1 2    2 3    3 1    1 2
    ->     ->     ->     -> and so on
3 4    1 4    2 4    3 4

That is, corners 1, 2 and 3 are moving counter-clockwise, whereas corner 4 stays still. The problem here is that not all configurations are obtained. The following three configurations are not obtained (and it may so happen that one of them may be the desirable one):

2 1       3 2       1 3

3 4       1 4       2 4

So what are we to do? Should we learn yet another algorithm? Should we discard this algorithm altogether? Is there a way to use this algorithm successfully? Well, yes, as I discovered. If we turn the upper layer appropriately, we will be able to place not one but two corners in their correct place. These correct corners will be either next to each other or diagonally placed from each other. Let us see how we can proceed in each case, with only the use of the U R Ui Li U Ri Ui algorithm, in order to successfully complete the second step of the second method:

First case: The two correct corners are next to each other

If the two correct corners are next to each other, I found that we can use the algorithm U R Ui Li U Ri Ui L only once to place all corners in their correct positions. The solution that I discovered is that we have to orient the cube in a way so that the two correct corners are in the upper back, away from us and then perform the algorithm.

In the following examples, A and B are the correct corners and 1 and 2 are the corners that are not in their correct positions and have to exchange place. The solution that I came up with, as I mentioned already, starts by orienting the cube so that A and B are at the back, and then finishes by performing the algorithm.

A B    B 1                                       A B
    ->     success: by turning the layer we have
1 2    A 2                                       2 1    

So the two incorrect corners changed placed and the upper layer is ready to be turned to its correct position relative to the bottom layer. Success! The second step of the method is complete!

What would have happened, if we would not follow my advice of putting A and B in the back? The other three orientations we can start with are:

B 2    2 A
    ->     disaster: A and B are no longer adjacent
A 1    B 1

2 1    1 B
    ->     disaster: A and B exchanged places
B A    2 A

1 A    A 2
    ->     disaster: A and B are no longer adjacent
2 B    1 B

So I just gave you all four orientations of the upper layer and the result we get when we apply the algorithm starting from each orientation. I discovered the correct orientation at first not by examining all orientations as I did now, but by understanding the effect of the algorithm. I observed the first orientation, the correct one with the A and B in the back and understood that when we apply the algorithm, corner 1 goes to the place B occupies and also (and here is the important part) A and B move together and without exchanging places. This was the “a-ha moment” for me.

Second case: The two correct corners are in a diagonal

If the two correct corners are diagonally placed, the solution that I discovered is that we have to orient the cube so that one of these correct corners is in the upper right front. Let us again study what happens when we apply the algorithm to the four possible orientations of the layer. A and B are the correct corners and 1 and 2 are the corners that are not correct (i.e. they need to change places).

A 1    1 2
    ->     success: 2 and B are now correct and adjacent
2 B    A B

1 B    B A
    ->     disaster: no corner is now correct
A 2    1 2

B 2    2 1
    ->     success: 1 and A are now correct and adjacent
1 A    B A

2 A    A B
    ->     disaster: no corner is now correct
B 1    2 1

In the first orientation we have one of the correct corners (corner B) in the upper right front. After the algorithm is applied, corner B and corner 2 are correct, whereas corner A and corner 1 are not. We messed up corner A in order to fix corner 2. But now we have two correct adjacent corners (B and 2), so we can apply the algorithm again as I described in the first case.

The same happens for the third orientation, whereas the second and the fourth orientation do not end up nicely after the application of the algorithm. Thus, in this case, we conclude that, before the application of the algorithm, we have to orient the cube so that one of the correct corners is in the upper right front. We then apply the algorithm and after that, we proceed as I described in the first case (where the two correct corners are next to each other).

Final notes

So there you have it: two methods for solving the 2X2. Each method requires knowledge of only two algorithms. This was my first and foremost concern: fewer algorithms and cases to remember (the downside being that we need to perform more turns until the cube is solved).

This guide is also useful for the 3X3. This is how you solve the whole of the 2X2 and how you also solve the corners of the 3X3. So, if you need a beginner’s guide to only help you with the corners of the 3X3, you can use this guide.

Happy cubing and keep in mind that a solved cube is a cute cube (yes, yes, you have to endure this lame joke, too).

The young and the RESTful

Wow, that’s a slap in the face of those incorrectly characterizing not RESTful APIs as RESTful! The year is 2008 and Roy Fielding is rightfully upset to see some authors of web applications incorrectly characterizing their applications as RESTful. He blogs about it in his blog post “REST APIs must be hypertext-driven”.

To answer Roy’s rhetorical question: No, I do not think that there is some broken manual somewhere that needs to be fixed

But in his groundbreaking dissertation about REST, Roy Fielding does not provide any counterexamples. I mean, he describes everything about REST, he leaves nothing out, he denotes its sharp contrast with RPC, he explains exactly how REST applications should be made and notes REST’s benefits and shortcomings. But counterexamples are also needed, like architectural decisions that are not RESTful, HTTP responses that are not RESTful and anything else that can show where things can go wrong.

When Roy Fielding wrote his dissertation, it is understandable that he did not expect such wide misuse of the REST architectural style. But now that he has observed it, he could provide us with counterexamples. He should not only just restate the REST principles, but also show examples of their incorrect use and how one could go on about restoring “RESTfulness”.

Since the REST architectural style is young, many implementations of it would be incorrect. The young and the RESTful. Oh, well…

I have just read Kelly Sommer’s excellent blog post “Clarifying REST“, which does exactly what I described here. An example that is not RESTful is provided and then a modification that makes it RESTful is presented. Sheer brilliance. Not only that, Kelly Sommers also provides an insightful analysis about the REST architecture and the REST constraints, i.e. its characteristics. But the thing that impressed me most is the post’s fairness and balance. Kelly Sommers points out that REST is one of the available architectural models and you do not have to abide to it, if you feel that another approach will be better in your case. It is when you declare that your application is RESTful that you have to follow all the REST rules.

Although REST concepts deserve a lot of discussion in order for someone to grasp them and also realize when she steers away from them, here is a rule of thumb that I picked up from Roy Fielding’s blog post: Apart from the knowledge of the initial URI to connect to, the client should have no other knowledge of the application. The client should be able to achieve everything it is supposed to just by relying on the URIs that are provided by the HTTP responses of the server.

Read my lips: no cookies. And another thing that is equally important: the server should have or retain no knowledge of state.

In magic, it is all done with strings and mirrors. In REST, it is all done with URIs.

Steve Jobs has left the building

Steve Jobs resigns As CEO Of Apple? Well, good riddance.

I am sorry to hear he has health issues. From the bottom of my heart, I wish him all the health in the world. The big C picked a tough nut to crack this time.

Nonetheless, it is a relief to see Apple dismantle, even if only somewhat. To me, Steve Jobs is the person that made it possible for every <insert demeaning characterization here> to think he or she is superior, just by using Apple’s products. In my opinion, quite the opposite is true.