erwan

It's a classic topic of study in the field of distributed systems.

The overarching goal is consensus between agents (e.g servers) over the state of the system.

For example, suppose that you want to achieve atomic consistency (i.e at any point in time the committed/persistent state of the system is homogeneous across all live nodes) in a private cluster replicating a database. The incoming requests are routed randomly to any node in your cluster. You have a synchronization mechanism (a consensus algorithm - like any-Paxos, Raft, Viewstamped Replication etc.) that lets you get this cluster of machines to agree on the state of the database. This is useful if you want fault-tolerance. The synchronization part is the consensus. The agents have to agree on the state-transition.

Now, observe two things:

1. This is a private cluster you own. In other words, you can make all the machines run the same software, trust each other, and assume they act on a best effort basis.

2. The failure model is "fail-stop". If a machine encounters some kind of failure, it won't exhibit arbitrary behavior but rather crash immediately. And you do not consider the case where a machine is taken over and tries to mess with the rest of the cluster in order to violate the desired safety guarantee (atomic consistency).

Obviously, these works if you are a privately own company and can spend resources hardening the parts of your network that are susceptible to be taken over. In a private setting, these assumptions are sufficient even though they are weak and optimistic. In practice, this is not so much an issue.

This falls apart however when you are in an adversarial setting and when your cluster is an open and public network that anyone can join or leave at any point in time. In that model, malicious actors can also show-up and exhibit/fake any kind of failure they want (e.g re-order messages, lie on their internal state, attempt to spoof other agents etc.). In that case, we say the fault-tolerance model is Byzantine. We go one level above in difficulty from the comfortable fail-stop assumption.

That's the gist of what Byzantine fault-tolerance is about. It defines the ability of a distributed system to resist a subset of its network trying to break consensus by any means possible as long as a sufficient majority remains honest.

For years, the major result on Byzantine Fault-Tolerance (BFT) had been a system called PBFT which although innovative and first of its kind, suffered several limitations. One of them was that any node in the network needed to have a complete list of the other nodes in the network, another was high-overhead, and communication complexity.

The innovation of Bitcoin cannot be explained without providing full-context of many different topics (defining asynchronicity, FLP result etc.) but the crux of it is that it offered a way to circumvent these limitations by massaging some of the requirements and cleverly aligning incentives such that you get a system where: 1/ safety is preserved even in an adversarial setting 2/ anyone can join/leave 3/ you get some degree of asynchronicity, 4/ many other things.

I realize this cannot be a satisfactory or exhaustive exposition of all the innovation that Bitcoin introduces but that would turn this comment into x10 its current length.

Thanks for sharing, this is a fascinating topic I just started investigating. Check out "Calculating Space" by Konrad Zuse (the inventor of the first programmable computer). Coincidentally, he published in 1969 - "The Laws of Form" was published the same year.

Link: ftp://ftp.idsia.ch/pub/juergen/zuserechnenderraum.pdf

The Theory of Computation

vs.

The Theory of Computation

That's a bit unfair, Hopcroft and Ullman is extensive and detailed by design. They invented the field AFAIK so this book ought to be deep as they use it to lay its foundations. If you - or lurkers - are looking for a solid, down-to-earth exploration of automata theory - but not so much proofs, then I would recommend these in no particular order:

- "Introduction to the Theory of Computation" [Part I] by M. Sipser

- "Introduction to Compiler Design" by Torben A. Mogensen

- "An introduction to Formal Languages and Automata" by P. Linz

- "Languages and Machines" by Thomas A. Sudkamp

>Many of OP's objections come off as petty

I have had the book in my hands, I have turned the pages and seen the typesetting myself. It's not an exaggeration. It looks like one of those books written by a typewriter with some of the lines are misaligned, except it wasn't and that is overall a pain to parse. Also the pages are small and margins wide.

Why inflict that upon yourself when there are plenty of other books that show a modicum of effort in editing.

What a coincidence.

Last week, I had a midterm that covered formal languages and automata theory. I went to the Davis Centre Library at the University of Waterloo looking for books on Automata Theory. I stumbled upon that very book. And though I dismissed it because the formatting was horrible, I did notice its odd epigraphs. I found the cover a bit mysterious and amusingly out of place, and went with something else.

Now, I read here on Hacker News, a high-profile website, about this most obscure review of this most obscure book written almost ten years ago - what's more? The person who wrote the review is also the one that requested that the library orders the book in the first place. He is one of my professors. Quite frankly the personification of what you would hope a scholar and teacher to be.

I know I have no reasons to feel agitated but why do I feel like this is the prologue of a thriller?

My pleasure! Could you give a high-level description of what is the problem/angle you are approaching?

Sharing this paper because effective workload simulation is a necessary step toward the Holy Grail: workload aware and self-tuning caches. In plain english, that means a cache that can adjust its parameters so that it is most effective for a given workload. Ideally, you want all of that without human supervision or pre-trained models, and in its fully accomplished form the cache can provision resources if it is worth it. Note that effectiveness here is traditionally measured in terms of hit:miss ration but other metrics exist too.

That's part of the broader idea of "intelligent systems" pro-actively adjusting themselves (resources, internal structure, overall policies) to the workload they are fed in order to optimize performance or cost-effectiveness.

The most basic caches have static eviction policies (e.g LRU/LFU), there has been some work on adaptive eviction policies (e.g ARC), and more recently on a clever combination of adjusting eviction policies and admission policies (e.g TinyLFU). The overarching goal of this line of research is to figure out a "silver bullet" cache which perform optimally (or close-to) regardless of R/W distributions by scrambling between different policies wrt. admission and eviction.

I think there is a lot of value in working on visual/reactive representation of algebraic structures. I have stopped counting the number of times I spent toiling on a result to understand its "depth" only to realize that much of that so-called depth comes from the narrow perspective from which I am contemplating it.

A good amount of undergraduate mathematics is exactly that: working on fundamental results long enough and deeply enough that you get a coherent mental model that lets you manipulate, compose, and spot them.

It seem to me that most of the attempts at visual mathematics fall short of not being general enough to capture different sorts of objects or ideas, or not in a way that is visually helpful anyway. And I'm thinking maybe this has more to do with the expressiveness of the visual medium rather anything else. Maybe images/visuals are just not powerful enough to map with these objects, maybe you need something at least as powerful as the "physical world" (albeit with different law of physics - dependent on the system you are studying). Example: the same way you cannot match the language of matched parenthesis with anything less powerful than a CFG.

Now, this is speculative and a conjecture: suppose that you have a perfectly immersive VR world, then could you find a way to perfectly match the axiomatic system+semantics/syntax of a mathematical object (e.g a Field) to a visual representation along with some physical rules (e.g 1+1=0) such that your actions in that world are always sound and correct with respect to the mathematical object it maps to.

I doubt it. It was open-sourced a few months ago and take some time to wrap your head around, at least for me.

edit: In fact, it is much older than that as dang pointed out.

True. I do find artistic obscenities fascinating, in particular when they look anachronistic. It's impressive than such an old artwork has survived time long enough despite featuring such sulfurous content.

And speaking for myself, it's not that I did not think of them as incapable of moral wrong doings - Antiquity was clearly a brutal period - or producing provocative work. But, I would have expected them to be more prude and limited in their ability to deliver artistic "shock value".

Well, I was wrong! They were very well capable of crude depiction and unsettling vulgarity - even for our contemporary standards!

That's arguably not the most interesting architectural aspect of Git.

Or does any back-linked tree data-structure becomes interesting if the nodes keep a hash of their parent instead of a raw reference? I don't think that's the case.

It might be a bit heretical but I don't think Git has a super interesting internal architecture. I'm not downplaying the fact that Git was very innovative, especially considered the landscape of SVMs at the time. The tool as a whole is great and has desirable properties but its internals don't strike me as particularly innovative. It's a clever composition of solutions to well established problem domains. And in that aspect it is a beautiful engineering solution although there is room for a lot of improvement in terms of UX.

And in addition to that, I would argue that it would be a very weak definition of "blockchain". The innovation in Bitcoin is the incorporation of proof-of-work and resulting alignment of incentives such that it can achieve probabilistic consensus in an adverse setting and with some degree of asynchronicity.

The underlying structure of the data is an obvious choice because it is simple and "captures" the idea of aggregate global state, but it's also hardly an important innovation. UTXOs are more significant.

And also, recall that the textbook example for state-machine replication is always an append-only log for example. So that's not the crux of it, or of blockchain, in my humble opinion.

I have had a positive experience so far at my school. The curriculum is coherent and the courses build onto each other nicely. It is challenging but the depth you get is well worth it IMO.

In fact, I was thinking the other day that my experience runs contrary to almost everything I read about the state of Computer science education online. Professors can show varying degree of commitment to the course but the baseline is quite high.

The majority of my instructors put more effort than they could get away with into the course: extra office-hours, staying late to answer questions, enriching material, original content, proactive on Piazza etc.

I found myself improving a lot as an engineer so here's a positive experience for you.

+1 for Biscuit and Fuchsia

I have sympathy for the author's frustration but they open-sourced their work under a very permissive license.

It sounds comical that suddenly something becomes valuable because you hang it in a gold frame, make minor modifications to it and ascribe it some symbolism. But that is exactly how contemporary artworks are done.

If you go to exhibits and auctions, it is not uncommon to see highly valued work that requires little sophistication to produce. The days you would woo the art world by technical mastery alone are (mostly) over. This story fits in the greater trend and there might be a bit of a culture clash.

I'm inclined to think that the general public underestimate contemporary art and the art world overestimate its superiority over the more conventional works. Whether it is for better or worse, I will leave you judge of that.

I love Rust, but in all honesty I wouldn't use it vs. Golang or C++17 for something that isn't a critical system (e.g a cryptography lib) and even then I'm not sure I wouldn't use something like OCaml instead.

The curve to productivity seem way too steep for the payoff.

I took that as a reference to pager duty.

I had a similar experience at Waterloo. The first semester of class we used Racket, HTDP (linked above) and even Haskell. I had already some experience with programming but it was like starting all over again to build solid foundations. If you are in the business of teaching introductory computer science material, I suggest you consider "How to design programs". Fun, good times.

https://www.student.cs.uwaterloo.ca/~cs145/experienced.shtml

If you have a genesis block with a hard-coded initial allocation of tokens, to me that counts as a premine.

Now I agree that you can make that premine "fair" and that there is some semantic cleaning to do.

Pre-mining is unpopular because when the first Bitcoin forks appeared, it became the modus operandi of scammers abusing the markets and the honest miners burning resources to operate the network.

I think it is a complete different story when a project has a pre-mine that is held by a formed legal structure with a fiduciary duty to spend the resources on the project's development. Obviously in pure proof-of-stake systems, a "pre-mine" is de facto the only path you can take.

Fairly distribute tokens is a problem that lacks a completely satisfying solution. It should be noted that "fairly" doesn't mean "evenly".

A fair distribution is one that lets the demand shape the final supply of tokens. In other words, you let people take the position and degree of investment they want to take without manipulating the supply to force pressure the demand.

Writing this comment gave me pauses, I hope that I conveyed my points clearly. Let me know if you need me to clarify anything.

Can you elaborate on the solution? Do you use an aggregator node, or have you massaged real-time reqs to allow for an aggregation period on the client side? I'm super curious to hear how you proceeded!

This decision has officially nothing to do with tax evasion/optimization. It is on grounds of consumer protection that Uber's licence is not being renewed.

Anyone who has taken a black cab should immediately understand the hypocrisy motivating this decision. The user experience is absolutely horrendous and there's no good tracking system to make black cab drivers accountable. In short, as everyone knows, it is just another artificial monopoly enshrined into law by regulators.

A good thing is that same regulators are losing lots of credibility. For decades they could pretend they were acting on basis of consumer protection. Now it is clear they aren't. People love Uber (not necessarily applies in the US anymore) because the experience is amazing at decent prices. Even in a city with a high density public transportation system like Paris, you are always happy to have that option in case it is past 1:00am or you're in a hurry.

It's an honest mistake, things like this happen. Not the end of the world, especially for an otherwise great product like chess.com.

Go easy on your eng team ;)

Coincidentally, a couple months ago one of my professors told me about James Hamilton, apparently, they met when he was studying at Waterloo. I started reading his blog.

This guy is brilliant. And his comments are often gems. The articles are good too but think of them as conversation openers. The real deal is in the comments imho. I recommend it. A somewhat funny article is about Zynga, the "prodigal kid" who left AWS for on-premises, only to come back later: http://perspectives.mvdirona.com/2015/05/the-return-to-the-c...

In the comments, he debunks (or take a shot at it) the idea that cloud providers like AWS aren't a good fit for organizations which have massive, but stable workloads.

This guy is so cool. I only wish he had more time to write.