Both providers and consumers of distributed storage services benefit from the quantification of the severity of consistency violations. However, existing methods fail to capture a typical pattern of violation - the disorder among operations with reference to the ideally strong atomic execution. Such disorder are often seen in Internet applications based on distributed storage services, such as instant messaging. To this end, we use inversions in a permutation with reference to the totally-ordered permutation to measure the consistency of data. The @math -atomicity model is proposed and a (pseudo-)polynomial verification algorithm for a restricted type of histories is proposed. The basic idea of the verification algorithm is brute-force search of the permutation with less than @math inversions, which requires exponential cost. Reasonable assumptions abstracted from applications scenarios can be leveraged to prune the search space, which yields an efficient polynomial verification algorithm.
Both @math -AV and @math -AV are NP-Complete in the general case, since they include the verification of atomicity as its special case. Read-mapping is used to circumvent the NP-Completeness of atomicity verification @cite_9 . Assuming read-mapping, the @math case for @math -AV is solved in @cite_15 . For @math , the @math -AV problem is solved only for special cases. Similarly, we also assume the existence of read-mapping, and solve the @math -AV problem for a restricted type of histories. For fixed @math and @math , the problem of proving NP-Completeness for @math -AV and @math -AV for are principally open.
@cite_9 @cite_15
2088419249 1596450573 2141368734 2807350215
Many NP-complete constraint satisfaction problems appear to undergo a “phase transition” from solubility to insolubility when the constraint density passes through a critical threshold. In all such cases it is easy to derive upper bounds on the location of the threshold by showing that above a certain density the first moment (expectation) of the number of solutions tends to zero. We show that in the case of certain symmetric constraints, considering the second moment of the number of solutions yields nearly matching lower bounds for the location of the threshold. Specifically, we prove that the threshold for both random hypergraph 2-colorability (Property B) and random Not-All-Equal @math -SAT is @math . As a corollary, we establish that the threshold for random @math -SAT is of order @math , resolving a long-standing open problem. In the generalized Russian cards problem, we have a card deck @math of @math cards and three participants, Alice, Bob, and Cathy, dealt @math , @math , and @math cards, respectively. Once the cards are dealt, Alice and Bob wish to privately communicate their hands to each other via public announcements, without the advantage of a shared secret or public key infrastructure. Cathy should remain ignorant of all but her own cards after Alice and Bob have made their announcements. Notions for Cathy's ignorance in the literature range from Cathy not learning the fate of any individual card with certainty (weak @math -security) to not gaining any probabilistic advantage in guessing the fate of some set of @math cards (perfect @math -security). As we demonstrate, the generalized Russian cards problem has close ties to the field of combinatorial designs, on which we rely heavily, particularly for perfect security notions. Our main result establishes an equivalence between perfectly @math -secure strategies and @math -designs on @math points with block size @math , when announcements are chosen uniformly at random from the set of possible announcements. We also provide construction methods and example solutions, including a construction that yields perfect @math -security against Cathy when @math . We leverage a known combinatorial design to construct a strategy with @math , @math , and @math that is perfectly @math -secure. Finally, we consider a variant of the problem that yields solutions that are easy to construct and optimal with respect to both the number of announcements and level of security achieved. Moreover, this is the first method obtaining weak @math -security that allows Alice to hold an arbitrary number of cards and Cathy to hold a set of @math cards. Alternatively, the construction yields solutions for arbitrary @math , @math and any @math . We present the first formal mathematical presentation of the generalized Russian cards problem, and provide rigorous security definitions that capture both basic and extended versions of weak and perfect security notions. In the generalized Russian cards problem, three players, Alice, Bob, and Cathy, are dealt a deck of @math cards, each given @math , @math , and @math cards, respectively. The goal is for Alice and Bob to learn each other's hands via public communication, without Cathy learning the fate of any particular card. The basic idea is that Alice announces a set of possible hands she might hold, and Bob, using knowledge of his own hand, should be able to learn Alice's cards from this announcement, but Cathy should not. Using a combinatorial approach, we are able to give a nice characterization of informative strategies (i.e., strategies allowing Bob to learn Alice's hand), having optimal communication complexity, namely the set of possible hands Alice announces must be equivalent to a large set of @math -designs, where @math . We also provide some interesting necessary conditions for certain types of deals to be simultaneously informative and secure. That is, for deals satisfying @math for some @math , where @math and the strategy is assumed to satisfy a strong version of security (namely perfect @math -security), we show that @math and hence @math . We also give a precise characterization of informative and perfectly @math -secure deals of the form @math satisfying @math involving @math -designs. We show that any language in nondeterministic time @math , where the number of iterated exponentials is an arbitrary function @math , can be decided by a multiprover interactive proof system with a classical polynomial-time verifier and a constant number of quantum entangled provers, with completeness @math and soundness @math , where the number of iterated exponentials is @math and @math is a universal constant. The result was previously known for @math and @math ; we obtain it for any time-constructible function @math . The result is based on a compression technique for interactive proof systems with entangled provers that significantly simplifies and strengthens a protocol compression result of Ji (STOC'17). As a separate consequence of this technique we obtain a different proof of Slofstra's recent result (unpublished) on the uncomputability of the entangled value of multiprover games. Finally, we show that even minor improvements to our compression result would yield remarkable consequences in computational complexity theory and the foundations of quantum mechanics: first, it would imply that the class MIP* contains all computable languages; second, it would provide a negative resolution to a multipartite version of Tsirelson's problem on the relation between the commuting operator and tensor product models for quantum correlations.