dadkins

x = new(foo) ... x = nil

There. Manual memory management. What? It's not as if when you free() something that was malloc()'ed, it gets returned to the operating system right away. It just goes back on the free list. Garbage collection amortizes that.

What are you waiting for? Just try it! There are already many public packages (see http://godashboard.appspot.com/package), and a tool called goinstall. And there's tons of community involvement, if you'd have a look at the mailing list.

Yes, they all use Adler32 instead because it's faster.

Actually, according to your own blog post on the subject, Gilbert and Lynch define a partition tolerance as:

    “The network will be allowed to lose arbitrarily many messages sent from one node to another”

There's a huge world of difference between the network losing arbitrarily many messages, and the definition you use elsewhere in this thread: namely, any subset of packets dropped, no matter how small, counts as a network partition.

Are you sure? Availability in the CAP theorem is a state, as are (P)artition and (C)onsistency. Your system can't be simultaneously consistent and available in the presence of a network partition. The A in CAP doesn't mean always available. It just means the system can, at best, be any two of the three at a time.

How do you explain Paxos, then? How does a dropped packet prevent the system from responding to queries? How about if I broadcast every response 10 times to everyone I know? How many packets must be dropped for the system to be considered unavailable?

Of course it will become either unavailable or inconsistent (or both) during a network partition. That's the essence of the CAP theorem.

But what does it mean to tolerate a partition? As if the system has a choice?

Any CA system is claiming to be consistent and available as long as the network doesn't partition. That's the strongest statement you can make under the CAP theorem, and Paxos certainly falls in that camp.

My problem with the original article was that it claimed that any individual network or node failure was a partition affecting the consistency or availability of the system. Paxos is a clear counterexample to that, as it tolerates a lot more than that without sacrificing consistency or availability.

Once the network actually partitions (or half the nodes become unreachable), then you are correct. The CAP theorem comes into play again and we must sacrifice either C or A, and Paxos chooses A.

Paxos is the quintessential example of a highly available, consistent system. It is available as long as more than half of the nodes are up and able to communicate with each other. It remains consistent, regardless of the failure pattern. You really do only have to worry about a true network partition. This isn't a probabilistic argument in any sense.

Not quite. What I'm saying is that a dropped packet or a failed node are not partitions as far as the CAP theorem is considered.

A distributed system is considered available if "every request received by a non-failing node [results] in a response." It does not mean you cannot retransmit or retry.

Similarly, the consistency guarantee only requires that there exist a total order on operations. Failures are ok, as we're allowed to retransmit, retry, and otherwise tolerate faults. There is no inconsistency, nor is anything eventual.

My point is that a "temporary" partition is just a fault, and as long as the fault is shorter than the allowed response time of the system, it doesn't make a difference.

I think the author, like many recently exposed to the CAP theorem, is confused about the meaning of partition tolerance, leading to ridiculous conclusions.

Partition tolerance does not mean your distributed system can't be consistent and available because your network dropped one packet, or one node failed. What would be the point of such a definition? Instead, the CAP theorem implies that while the network is partitioned, consistency or availability must be sacrificed. In the case of the dropped packet, once it is retransmitted the partition is healed and progress can be made. Or in the case of the failed node, nothing says that the rest of the system can't be consistent and available, so that the system as a whole maintains that property. There is no requirement that the unavailable node be available.

Truly partition tolerant systems are those that continue to function in the face of a prolonged partition, and those are the systems that must sacrifice either consistency or availability.

/Unfortunately almost none of the results ever trickled through to the kernel development community, not to mention actually working code being submitted to the Linux kernel mailing list./

Unfortunately, when an academic submits their working code to the Linux kernel mailing list, they're likely to get flamed to a crisp if they get any response at all. They learn real quick not to waste their time with that hostile crowd.

Not to mention the volume of the Linux kernel mailing list is absurd. Who has the time or inclination to keep up if it's not their main passion?

I should add that it's the massive network switch that makes this all possible. You can scale disk I/O by adding disks, and you can scale in-memory sorting by adding cores and memory. But it's awfully expensive to buy your way out of a bottleneck in your network when everyone needs to talk to each other at full speed.

It's hardware. They have have 52 servers, each with 16 disks which I assume are capable of I/O at 100MB/s. That's an aggregate disk I/O rate of 83.2 GB/s. Their network switch provides 10Gbps connectivity between each pair, which implies they can move data between nodes at 65 GB/s. With that hardware setup they can read 1TB from disk and distribute in around 15 seconds. They can write sorted data back to disk in 12 seconds. That leaves a little over 30 seconds for each node to sort 19.2 GB in memory. But each node has 8 cores, so each core has to sort 2.4 GB in 30 seconds. I've seen Burstsort chew through that amount of data in half the time.

More recently (from Wikipedia):

"In 1999, a number of groups successfully sued Kaiser Permanente in regard to its In the Hands of Doctors advertising campaign. The lawsuit revealed that doctors at the organization were not fully in control of decision-making and that there may have been persuasion to limit care with financial bonuses."

Ehrlichman: “Edgar Kaiser is running his Permanente deal for profit. And the reason that he can … the reason he can do it … I had Edgar Kaiser come in … talk to me about this and I went into it in some depth. All the incentives are toward less medical care, because … the less care they give them, the more money they make.”

President Nixon: “Fine.”

> Nope. You haven't thought this through.

That's not really fair. Paxos provably addresses all of the missing ack problems you suggest and makes progress as long as a quorum of nodes can communicate with each other. That's why I mentioned it.

I'm also aware of the problems with two phase commit, namely the single point of failure. Funny enough, Paxos Commit is the solution to that problem.

So really, Paxos is a magic wand when it comes to available and consistent distributed systems. You shouldn't use it for every single update in your distributed database; it's way too much overhead. But somewhere in the system there's probably some algorithm that looks like Paxos handling some important piece of metadata or the system isn't truly fault-tolerant.

The link you gave is consistent with what I've said. Namely, the concept of quorum is a way to sacrifice availability for the minority of nodes in the presence of a partition but otherwise remain consistent. Paxos does precisely that. It's consistent and available in the absence of partitions, and it sacrifices availability for some in the presence of a partition.

By the way, the other possibility in the design space is to remain available but sacrifice consistency in the face of a partition. This is the eventual consistency camp.

A washed out bridge.

> A Consistent/Available system means that reading and writing always works the way you expect, but if one node fails the whole system stops working.

I've seen this mistaken statement several times now and it really bugs me. A consistent/available system can't tolerate partitions, i.e. a split in the network. However, it can certainly tolerate a single failure and remain consistent and available. That's the whole point. A trivial system with these properties is one that replicates every update to all available nodes and requires reads to get matching results from at least half of the nodes. Paxos is another example.

That's strange that you suggest master/slave replication as a way to achieve consistency and availability. If you lose your master, you can't take writes and are thus no longer available. And if your slaves are behind the master, then reads from the slave are stale, definitely not consistent with the master.

Yes, indeed. Spot the buzzword:

We make social games.

a social data request and fulfillment system

adding social data

leveraging social media

identify active social networkers

Infoharmoni visualizes the real-time social web

social sports (and soon pop culture) betting applications

I wondered that too. My best guess is that range of signed/unsigned char both fit in signed ints, so there's no ambiguity in promoting them to ints.

I was skeptical about his example of a compiler bug. Take the following similar example:

    int bar(void) {
        unsigned x = 1;
        int y = -1;
        return x > y;
    }

Surprisingly, the result is always 0, at least on every version of gcc I've tried. How could this be? It turns out unsigned's are one area where the C standard really screwed up. When comparing a signed and an unsigned value, the compiler helpfully promotes the signed (-1) to unsigned.

I was surprised the given example with chars instead of ints didn't give the same result. Was it really a bug, or just ambiguity in the standard?

Yes, it's lazy. The sieve outputs on a channel, which blocks until you read it. It will only generate more numbers as they're consumed. Same thing with the filters.

1960s?

C. A. R. Hoare, ``Communicating Sequential Processes,'' Communications of the ACM 21(8) (August 1978), 666-677.

I decided to try to figure it out from this angle. What we have is a random walk where, with probability 0.51 we go forward, and with probability 0.49 we go backward. If we ever reach 10, we quit. I wrote a program to compute the cumulative probability that we stop at 10 over time.

  #include <stdio.h>
  #include <math.h>

  #define GOAL 10
  #define MAXN 20000

  double p = 0.51;
  double pr[2][MAXN + 1 + GOAL];

  #define PR_(t, x) (pr[(t) % 2][MAXN + (x)])

  int main()
  {
    int n, i;
    double totalp = 0;

    PR_(0, 0) = 1;
    for (n = 1; n <= MAXN; n++) {
        PR_(n, -n) = PR_(n-1, -n+1) * (1 - p);
        for (i = -n+1; i < GOAL; i++)
            PR_(n, i) = PR_(n-1, i-1) * p + PR_(n-1, i+1) * (1 - p);
        totalp += PR_(n-1, GOAL-1) * p;
        printf("n=%d p=%g\n", n, totalp);
        if (totalp >= 0.99)
            break;
    }

    return 0;
  }

The results:

  n=5488 p=0.989997
  n=5489 p=0.989997
  n=5490 p=0.990005

You get to quit much sooner if you can walk away as soon as you have $10!

Oh you're right, that's the solution. Silly me, the moment I go to a computer to solve the final equation I get it wrong!

Let X be a random variable indicating the number of heads that have come up. After n flips, E[x] = pn, where p = 0.51 in our case. When X >= n/2 + 5, we're up 10 dollars.

In other words, we want to find n such that

Pr[X < n/2 + 5] < .01

If we express that in terms of the mean, we can apply a Chernoff bound:

Pr[X <= E[X] - a] <= Exp[-2a^2/n], for 0 < a < E[X]

If E[x] = pn, then a = pn - (n/2 + 5), which for p = 0.51 is a = .01n - 5.

So, solving Exp[-2a^2/n] = .01 (with help from Wolfram alpha) gives a quadratic equation with two solutions:

n = 348.257 and n = 651.743

The first is too small, a would be negative (n needs to be at least 500). The second is good enough.

652 does the trick.