By "quadruped" I mean here a robot (or animal) with four legs used for walking. "Gait" is the actual way it moves those legs to walk. There is a lot of information about quadruped gaits, and I'm going to collect some notes about them here.
I'm going to concentrate on robots that have relatively small feet (think about spikes) and which don't touch the ground with their bodies (that would be a fifth leg). I will also assume they have three degrees of freedom per leg, so that they are able to reach any point within their range. It's possible to make walking robots with less degrees of freedom, but that would usually involve some slipping of the legs on the floor. I assume that once a leg is set down on the floor, it stays in that place, possibly rotating, but not changing the point of contact with the ground.
Generally speaking, the purpose of walking is to move your body from one place to another, while also keeping the balance. Unsurprisingly, most gaits can be divided into the forward motion of the body (or the "virtual vehicle" reference frame), and the movement of the legs that need to carry it.
In order for the robot to not fall down (for statically stable gaits), it has to keep its center of gravity inside the convex area around the surfaces of its feet that are touching the ground. In case of a four legged robot with point feet, that means that at least three legs have to be kept on the ground, and the vertical projection of the center of gravity must lie inside the triangle formed by their points of contact with the ground.
For dynamically stable gaits this is much more complicated, but the idea is similar – you want to move the body, while moving the feet to keep supporting it.
A gait is said to be "statically stable", if you can stop the robot at any moment during it, and the robot will not fall down. That also means that you can perform it arbitrarily slowly.
Since you need to keep the center of gravity of the robot above the area of the floor framed by its legs, and you only have four legs, it means that you can only move one leg at a time to remain stable. In addition, you might need to shift the body of the robot to remove weight from the leg that you are going to move. This family of gaits is sometimes called "ripple gaits", because of how they look in robots and animals with more legs.
There are only six possible orders in which you can move four legs one leg at a time. Actually, if you don't consider mirrored gaits, you are only left with three of them:
1 2 1 2 1 3 a b c 4 3 3 4 4 2
The last one, c, gives us the largest area of support and the best stability. That gait is called "creep gait", and that's how cats walk when they are stalking their prey.
There are several ways in which you can move the body of the robot forward while it is walking.
The most smooth is to just continuously move all the legs backwards at a constant speed while they touch the ground. You have to be careful to do it slow enough that you manage to make a step with each of them before they move outside their range though. In a cinch, you could pause that movement and wait for a leg to keep up.
Another way is to move the legs between the steps, when all four legs are on the ground. This lets you avoid the timing problems and is easier to program, but is slower.
At the other extreme to continuous motion, you could move the legs backwards only after all four of them have made a step. That is the slowest approach and looks quite jerky.
In any case, the speed of your forward movement is limited by two factors: the time a single leg needs to make a step, and the range of that leg – or more precisely, the distance between where it is taken off ground, and where it is put down.
We can categorize gaits by looking at the time between removing a leg from the floor, and removing the next leg in sequence. If that time is larger or equal than the time it takes to put the leg back, we have a statically stable gait. In particular, if that time is equal (the previous leg is put down at the same moment when the next leg is raised), the stability and speed are maximized and the gait is called a "singular gait".
But we can move beyond that, into the real of dynamically stable gaits. If this time is smaller than it takes to move the leg, we start having times when there are two legs in the air at the same time. If they move fast, the robot won't have time to become unstable, so the gait still works. As we decrease that time further, we arrive at a point where we have two legs on the ground at all times – that is called a "trot gait".
We can go further, and when we only have one or two legs touching the ground at a time, the gait is called "gallop". There are actually several different kinds of gallops, depending on the order in which the legs touch the ground, but we won't get into that in too much detail – getting your robot to balance properly while galloping is very difficult and we won't even try.
Depending on the physical construction of the robot – the size of its body, the length and locations of its legs, etc. – it may keep its center of gravity inside the support area naturally, or not. If it doesn't, we have to do some extra work to keep it stable – we need to move its center of gravity.
There are several possible approaches to that. We can have an additional "limb", such as a tail or a head, and move that for balance. We can have an additional joint in the body allowing us to bend it. Or we can just move the whole body by changing the posture of our robot.
We can sway to the sides, or to front and back, or we can combine those two movements in a sort of a figure eight (or a circle, depending on the gait) motion. One problem with this approach is that we need time to move such a mass. Since we can't start before the previous leg is on the ground, and have to finish before the next leg is taken off the ground – our gait has to be non-singular, with some time before steps taken to re-position the body. Of course, we could start before the leg touches the ground, and finish a little bit after the next leg is lifted – but then again our gait is dynamically stable, but not statically.