[John Doyle] The reason the bacterium works so well, Doyle finds, is that it is organized in much the same way as the Internet. Both the Internet and E. coli are conceptually organized like a bow tie, with a broad fan of incoming material flowing into a central knot and then flowing into another broad fan of outgoing material. On the Internet, the incoming fan is made up of data from a huge range of sources— e-mail, YouTube videos, Skype phone calls, and the like. In E. coli, the incoming fan is made up of the many sorts of food it eats. As information and food move into their respective bow ties, they get homogenized: E. coli breaks down its food into a few building blocks, while the Internet breaks down its motley incoming data streams into streams of standardized packets.

From the knot, both bow ties then fan out. E. coli turns its building blocks into DNA, proteins, membrane molecules, and any other special ingredient it needs. On the Internet, data packets reach a computer, where they can be reassembled into the original e-mail, YouTube videos, Skype telephone calls, and the like.

A bow-tie organization allows both the Internet and E. coli to run quickly and efficiently. If E. coli (like all bacteria, indeed like all living things) did not have a bow tie, it would have to use a different set of enzymes to make each of the thousands of different molecules it needs from each type of food. Rather than use such a huge, slow system, E. coli just points all its metabolic pathways into the same bow-tie knot, making everything from the same raw materials. Likewise, the Internet’s bow-tie architecture means that it doesn’t have different ways to handle, say, e-mail traffic and instant-message traffic. Everything passes through as the same types of data packets.

The bow-tie architecture also makes both the Internet and E. coli robust. If the type of incoming material changes rapidly—say, a surge in video traffic in the Internet’s case, or a new food source for the E. coli—the system can process that material without having to retool its entire metabolism to cope.

Another advantage of a bow tie is that it makes feedback control easy. Information travels back from a receiving computer to the sender, which can speed up or slow down its packets in response. E. coli’s metabolism is loaded with analogous feedback loops. Normally E. coli can synthesize all the amino acids it needs for making proteins. But if it can get a certain kind of amino acid from the environment, that information shuts down its own production line.

But as Doyle points out, improving robustness comes with a price. The bow-tie structure opens the door to a vulnerability that could prove very hard to fix. Because of the homogenization that occurs at the heart of the bow tie, it’s difficult to identify and block harmful agents. In the case of the Internet, it takes only a short piece of code to produce a digital virus that can spread quickly to millions of computers and cause billions of dollars of damage. In living organisms, real viruses hijack cells in much the same way.

Doyle thinks the similarity between E. coli and the Internet is no accident. As networks get big and complicated—either through the tinkering of Internet engineers or through millions of years of evolution—they must follow certain rules to stay robust. “There is an inevitable architecture,” Doyle says.

"Recent results about the robustness of kernel methods involve the analysis of influence functions. By definition the influence function is closely related to leave-one-out criteria. In statistical learning, the latter is often used to assess the generalization of a method. In statistics, the influence function is used in a similar way to analyze the statistical efficiency of a method. Links between both worlds are explored. The influence function is related to the first term of a Taylor expansion. Higher order influence functions are calculated. A recursive relation between these terms is found characterizing the full Taylor expansion. It is shown how to evaluate influence functions at a specific sample distribution to obtain an approximation of the leave-one-out error. A specific implementation is proposed using a L1 loss in the selection of the hyperparameters and a Huber loss in the estimation procedure. The parameter in the Huber loss controlling the degree of robustness is optimized as well. The resulting procedure gives good results, even when outliers are present in the data."

Recently, Bilu and Linial formalized an implicit assumption often made when choosing a clustering objective: that the optimum clustering to the objective should be preserved under small multiplicative perturbations to distances between points. They showed that for max-cut clustering it is possible to circumvent NP-hardness and obtain polynomial-time algorithms for instances resilient to large (factor $O(sqrt{n})$) perturbations, and subsequently Awasthi et al. considered center-based objectives, giving algorithms for instances resilient to O(1) factor perturbations.
In this paper, we greatly advance this line of work. For center-based objectives, we present an algorithm that can optimally cluster instances resilient to $(1 + sqrt{2})$-factor perturbations, solving an open problem of Awasthi et al. For a commonly used center-based objective $k$-median, we additionally give algorithms for a more relaxed assumption in which we allow the optimal solution to change in a small $epsilon$ fraction of the points after perturbation. We give the first bounds known for this more realistic and more general setting. We also provide positive results for min-sum clustering which is a generally much harder objective than $k$-median (and also non-center-based). Our algorithms are based on new linkage criteria that may be of independent interest.
Additionally, we give sublinear-time algorithms, showing algorithms that can return an implicit clustering from only access to a small random sample.

Abstract: "Scenarios play a prominent role in policy debates over climate change, but questions continue about how best to use them. We describe a new analytic method, based on robust decision making, for suggesting narrative scenarios that emerge naturally from a decision analytic framework. We identify key scenarios as those most important to the choices facing decision makers and find such cases with statistical analysis of datasets created by multiple runs of computer simulation models. The resulting scenarios can communicate quantitative judgments about uncertainty as well as support a well-defined decision process without many drawbacks of current approaches. We describe an application to long-term water planning in California."

Source: The World Bank (forthcoming). Economic Evaluation of Climate Change Adaptation Projects: Approaches for the Agricultural Sector and Beyond. Washington, DC: The World Bank.

"This paper considers the model introduced by Bilu and Linial (2010), who study problems for which the optimal clustering does not change when the distances are perturbed by multiplicative factors. They show that even when a problem is NP-hard, it is sometimes possible to obtain polynomial-time algorithms for instances resilient to large perturbations, e.g. on the order of $O(sqrt{n})$ for max-cut clustering. Awasthi et al. (2010) extend this line of work by considering center-based objectives, and Balcan and Liang (2011) consider the $k$-median and min-sum objectives, giving efficient algorithms for instances resilient to certain constant multiplicative perturbations.

Here, we are motivated by the question of to what extent these assumptions can be relaxed while allowing for efficient algorithms. We show there is little room to improve these results by giving NP-hardness lower bounds for both the $k$-median and min-sum objectives. On the other hand, we show that multiplicative resilience parameters, even only on the order of $Theta(1)$, can be so strong as to make the clustering problem trivial, and we exploit these assumptions to present a simple one pass streaming algorithm for the $k$-median objective. We also consider a model of additive perturbations and give a correspondence between additive and multiplicative notions of stability. Our results provide a close examination of the consequences of assuming, even constant, stability in data."

"We introduce a mechanism for generating power law distributions, referred to as highly optimized tolerance (HOT), which is motivated by biological organisms and advanced engineering technologies. Our focus is on systems which are optimized, either through natural selection or engineering design, to provide robust performance despite uncertain environments. We suggest that power laws in these systems are due to tradeos between yield, cost of resources, and tolerance to risks. These tradeos lead to highly optimized designs that allow for occasional large events. We investigate the mechanism in the context of percolation and sand pile models in order emphasize the sharp contrasts between HOT and self organized criticality (SOC), which has been widely suggested as the origin for power laws in complex systems. Like SOC, HOT produces power laws. However, compared to SOC, HOT states exist for densities which are higher than the critical density, and the power laws are not restricted to special values of the density.
The characteristic features of HOT systems include: (1) high eciency, performance, and robustness to designed-for uncertainties, (2) hypersensitivity to design aws and unanticipated perturbations, (3) nongeneric, specialized, structured congurations, and (4) power laws. The rst three of these are in contrast to the traditional hallmarks of criticality, and are obtained by simply adding the element of design to percolation and sand pile models, which completely changes their characteristics."

"..unlike systems designed for robustness, complex adaptive systems are systems in which whatever robustness exists has to emerge from the collective properties of the individual units that make up the system; there is no planner or manager whose decisions completely control the system...What leads to robustness in complex adaptive systems? There are at least two ways in which a system can be robust in the face of disturbances: by having a rigid design and reliable
components, or by having a flexible design that may also include replaceable components."

chapter 4 of Nassim Taleb's new book

"Microblogging services such as Twitter are an increasingly important way to communicate, both for individuals and for groups through the use of hashtags that denote topics of conversation. However, groups can be easily blocked from communicating through blocking of posts with the given hashtags. We propose #h00t, a system for censorship resistant microblogging. #h00t presents an interface that is much like Twitter, except that hashtags are replaced with very short hashes (e.g., 24 bits) of the group identifier. Naturally, with such short hashes, hashtags from different groups may collide and #h00t users will actually seek to create collisions. By encrypting all posts with keys derived from the group identifiers, #h00t client software can filter out other groups' posts while making such filtering difficult for the adversary. In essence, by leveraging collisions, groups can tunnel their posts in other groups' posts. A censor could not block a given group without also blocking the other groups with colliding hashtags. We evaluate the feasibility of #h00t through traces collected from Twitter, showing that a single modern computer has enough computational throughput to encrypt every tweet sent through Twitter in real time. We also use these traces to analyze the bandwidth and anonymity tradeoffs that would come with different variations on how group identifiers are encoded and hashtags are selected to purposefully collide with one another."

One of the first systems our engineers built in AWS is called the Chaos Monkey. The Chaos Monkey’s job is to randomly kill instances and services within our architecture. If we aren’t constantly testing our ability to succeed despite failure, then it isn’t likely to work when it matters most – in the event of an unexpected outage.

For many years the Robustness Principle was accepted dogma, failing more when it was ignored rather than when practiced. In recent years, however, that principle has been challenged. This isn't because implementers have gotten more stupid, but rather because the world has become more hostile. Two general problem areas are impacted by the Robustness Principle: orderly interoperability and security.