Lower Bounds for Achieving Synchronous Early Stopping Consensus with Orderly Crash Failures

In this paper, we discuss the consensus problem for synchronous distributed systems with orderly crash failures. For a synchronous distributed system of n processes with up to t crash failures and f failures actually occur, first, we present a bivalency argument proof to solve the open problem of proving the lower bound, min (t + 1, f + 2) rounds, for early-stopping synchronous consensus with orderly crash failures, where t < n - 1. Then, we extend the system model with orderly crash failures to a new model in which a process is allowed to send multiple messages to the same destination process in a round and the failing processes still respect the order specified by the protocol in sending messages. For this new model, we present a uniform consensus protocol, in which all non-faulty processes always decide and stop immediately by the end of f + 1 rounds. We prove that the lower bound of early stopping protocols for both consensus and uniform consensus are f + 1 rounds under the new model, and our proposed protocol is optimal.

Ω-results for Beurling's zeta function and lower bounds for the generalised Dirichlet divisor problem

In this paper we study generalised prime systems for which the integer counting function NP(x) is asymptotically well behaved, in the sense that NP(x)=ρx+O(xβ), where ρ is a positive constant and . For such systems, the associated zeta function ζP(s) is holomorphic for . We prove that for , for any ε>0, and also for ε=0 for all such σ except possibly one value. The Dirichlet divisor problem for generalised integers concerns the size of the error term in NkP(x)−Ress=1(ζPk(s)xs/s), which is O(xθ) for some θ<1. Letting αk denote the infimum of such θ, we show that .

Nonlinear saturation of baroclinic instability: part III: bounds on the energy

Rigorous upper bounds are derived on the saturation amplitude of baroclinic instability in the two-layer model. The bounds apply to the eddy energy and are obtained by appealing to a finite amplitude conservation law for the disturbance pseudoenergy. These bounds are to be distinguished from those derived in Part I of this study, which employed a pseudomomentum conservation law and provided bounds on the eddy potential enstrophy. The bounds apply to conservative (inviscid, unforced) flow, as well as to forced-dissipative flow when the dissipation is proportional to the potential vorticity. Bounds on the eddy energy are worked out for a general class of unstable westerly jets. In the special case of the Phillips model of baroclinic instability, and in the limit of infinitesimal initial eddy amplitude, the bound states that the eddy energy cannot exceed ϵβ2/6F where ϵ = (U − Ucrit)/Ucrit is the relative supercriticality. This bound captures the essential dynamical scalings (i.e., the dependence on ϵ, β, and F) of the saturation amplitudes predicted by weakly nonlinear theory, as well as exhibiting remarkable quantitative agreement with those predictions, and is also consistent with heuristic baroclinic adjustment estimates.

Rigorous bounds on the nonlinear saturation of instabilities to parallel shear flows

A novel method is presented for obtaining rigorous upper bounds on the finite-amplitude growth of instabilities to parallel shear flows on the beta-plane. The method relies on the existence of finite-amplitude Liapunov (normed) stability theorems, due to Arnol'd, which are nonlinear generalizations of the classical stability theorems of Rayleigh and Fjørtoft. Briefly, the idea is to use the finite-amplitude stability theorems to constrain the evolution of unstable flows in terms of their proximity to a stable flow. Two classes of general bounds are derived, and various examples are considered. It is also shown that, for a certain kind of forced-dissipative problem with dissipation proportional to vorticity, the finite-amplitude stability theorems (which were originally derived for inviscid, unforced flow) remain valid (though they are no longer strictly Liapunov); the saturation bounds therefore continue to hold under these conditions.

Extreme bounds of democracy

What determines the emergence and survival of democracy? The authors apply extreme bounds analysis to test the robustness of fifty-nine factors proposed in the literature, evaluating over three million regressions with data from 165 countries from 1976 to 2002. The most robust determinants of the transition to democracy are gross domestic product (GDP) growth (a negative effect), past transitions (a positive effect), and Organisation for Economic Co-operation and Development membership (a positive effect). There is some evidence that fuel exporters and Muslim countries are less likely to see democracy emerge, although the latter finding is driven entirely by oil-producing Muslim countries. Regarding the survival of democracy, the most robust determinants are GDP per capita (a positive effect) and past transitions (a negative effect). There is some evidence that having a former military leader as the chief executive has a negative effect, while having other democracies as neighbors has a reinforcing effect.

On statistical bounds of heuristic solutions to location problems

Solutions to combinatorial optimization problems, such as problems of locating facilities, frequently rely on heuristics to minimize the objective function. The optimum is sought iteratively and a criterion is needed to decide when the procedure (almost) attains it. Pre-setting the number of iterations dominates in OR applications, which implies that the quality of the solution cannot be ascertained. A small, almost dormant, branch of the literature suggests using statistical principles to estimate the minimum and its bounds as a tool to decide upon stopping and evaluating the quality of the solution. In this paper we examine the functioning of statistical bounds obtained from four different estimators by using simulated annealing on p-median test problems taken from Beasley’s OR-library. We find the Weibull estimator and the 2nd order Jackknife estimator preferable and the requirement of sample size to be about 10 being much less than the current recommendation. However, reliable statistical bounds are found to depend critically on a sample of heuristic solutions of high quality and we give a simple statistic useful for checking the quality. We end the paper with an illustration on using statistical bounds in a problem of locating some 70 distribution centers of the Swedish Post in one Swedish region.