Arrow Research search

Author name cluster

Cynthia Dwork

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

43 papers
2 author rows

Possible papers

43

NeurIPS Conference 2025 Conference Paper

How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension

  • Cynthia Dwork
  • Lunjia Hu
  • Han Shao

We study a fundamental question of domain generalization: given a family of domains (i. e. , data distributions), how many randomly sampled domains do we need to collect data from in order to learn a model that performs reasonably well on every seen and unseen domain in the family? We model this problem in the PAC framework and introduce a new combinatorial measure, which we call the domain shattering dimension. We show that this dimension characterizes the domain sample complexity. Furthermore, we establish a tight quantitative relationship between the domain shattering dimension and the classic VC dimension, demonstrating that every hypothesis class that is learnable in the standard PAC setting is also learnable in our setting.

PDF Details

STOC Conference 2024 Conference Paper

Complexity-Theoretic Implications of Multicalibration

  • Sílvia Casacuberta
  • Cynthia Dwork
  • Salil P. Vadhan

We present connections between the recent literature on multigroup fairness for prediction algorithms and classical results in computational complexity. Multiaccurate predictors are correct in expectation on each member of an arbitrary collection of pre-specified sets. Multicalibrated predictors satisfy a stronger condition: they are calibrated on each set in the collection. Multiaccuracy is equivalent to a regularity notion for functions defined by Trevisan, Tulsiani, and Vadhan (2009). They showed that, given a class F of (possibly simple) functions, an arbitrarily complex function g can be approximated by a low-complexity function h that makes a small number of oracle calls to members of F , where the notion of approximation requires that h cannot be distinguished from g by members of F . This complexity-theoretic Regularity Lemma is known to have implications in different areas, including in complexity theory, additive number theory, information theory, graph theory, and cryptography. Starting from the stronger notion of multicalibration, we obtain stronger and more general versions of a number of applications of the Regularity Lemma, including the Hardcore Lemma, the Dense Model Theorem, and the equivalence of conditional pseudo-min-entropy and unpredictability. For example, we show that every boolean function (regardless of its hardness) has a small collection of disjoint hardcore sets, where the sizes of those hardcore sets are related to how balanced the function is on corresponding pieces of an efficient partition of the domain.

Details

NeurIPS Conference 2024 Conference Paper

Order-Independence Without Fine Tuning

  • Reid McIlroy-Young
  • Katrina Brown
  • Conlan Olson
  • Linjun Zhang
  • Cynthia Dwork

The development of generative language models that can create long and coherent textual outputs via autoregression has lead to a proliferation of uses and a corresponding sweep of analyses as researches work to determine the limitations of this new paradigm. Unlike humans, these ' Large Language Models ' (LLMs) are highly sensitive to small changes in their inputs, leading to unwanted inconsistency in their behavior. One problematic inconsistency when LLMs are used to answer multiple-choice questions or analyze multiple inputs is order dependency: the output of an LLM can (and often does) change significantly when sub-sequences are swapped, despite both orderings being semantically identical. In this paper we present, a technique that guarantees the output of an LLM will not have order dependence on a specified set of sub-sequences. We show that this method provably eliminates order dependency, and that it can be applied to any transformer-based LLM to enable text generation that is unaffected by re-orderings. Delving into the implications of our method, we show that, despite our inputs being out of distribution, the impact on expected accuracy is small, where the expectation is over the order of uniformly chosen shuffling of the candidate responses, and usually significantly less in practice. Thus, can be used as a ' dropped-in ' method on fully trained models. Finally, we discuss how our method's success suggests that other strong guarantees can be obtained on LLM performance via modifying the input representations. Code is available at github. com/reidmcy/set-based-prompting.

PDF Details DOI

ICLR Conference 2021 Conference Paper

Private Post-GAN Boosting

  • Marcel Neunhoeffer
  • Zhiwei Steven Wu
  • Cynthia Dwork

Differentially private GANs have proven to be a promising approach for generating realistic synthetic data without compromising the privacy of individuals. Due to the privacy-protective noise introduced in the training, the convergence of GANs becomes even more elusive, which often leads to poor utility in the output generator at the end of training. We propose Private post-GAN boosting (Private PGB), a differentially private method that combines samples produced by the sequence of generators obtained during GAN training to create a high-quality synthetic dataset. To that end, our method leverages the Private Multiplicative Weights method (Hardt and Rothblum, 2010) to reweight generated samples. We evaluate Private PGB on two dimensional toy data, MNIST images, US Census data and a standard machine learning prediction task. Our experiments show that Private PGB improves upon a standard private GAN approach across a collection of quality measures. We also provide a non-private variant of PGB that improves the data quality of standard GAN training.

Details

ICML Conference 2020 Conference Paper

Interpreting Robust Optimization via Adversarial Influence Functions

  • Zhun Deng
  • Cynthia Dwork
  • Jialiang Wang 0001
  • Linjun Zhang

Robust optimization has been widely used in nowadays data science, especially in adversarial training. However, little research has been done to quantify how robust optimization changes the optimizers and the prediction losses comparing to standard training. In this paper, inspired by the influence function in robust statistics, we introduce the Adversarial Influence Function (AIF) as a tool to investigate the solution produced by robust optimization. The proposed AIF enjoys a closed-form and can be calculated efficiently. To illustrate the usage of AIF, we apply it to study model sensitivity — a quantity defined to capture the change of prediction losses on the natural data after implementing robust optimization. We use AIF to analyze how model complexity and randomized smoothing affect the model sensitivity with respect to specific models. We further derive AIF for kernel regressions, with a particular application to neural tangent kernels, and experimentally demonstrate the effectiveness of the proposed AIF. Lastly, the theories of AIF will be extended to distributional robust optimization.

Details

FOCS Conference 2019 Conference Paper

Learning from Outcomes: Evidence-Based Rankings

  • Cynthia Dwork
  • Michael P. Kim
  • Omer Reingold
  • Guy N. Rothblum
  • Gal Yona

Many selection procedures involve ordering candidates according to their qualifications. For example, a university might order applicants according to a perceived probability of graduation within four years, and then select the top 1000 applicants. In this work, we address the problem of ranking members of a population according to their "probability" of success, based on a training set of historical binary outcome data (e. g. , graduated in four years or not). We show how to obtain rankings that satisfy a number of desirable accuracy and fairness criteria, despite the coarseness of the training data. As the task of ranking is global (the rank of every individual depends not only on their own qualifications, but also on every other individuals' qualifications) ranking is more subtle and vulnerable to manipulation than standard prediction tasks. Towards mitigating unfair discrimination caused by inaccuracies in rankings, we develop two parallel definitions of evidence-based rankings. The first definition relies on a semantic notion of domination-compatibility: if the training data suggest that members of a set S are more qualified (on average) than the members of T, then a ranking that favors T over S (i. e. where T dominates S) is blatantly inconsistent with the evidence, and likely to be discriminatory. The definition asks for domination-compatibility, not just for a pair of sets, but rather for every pair of sets from a rich collection C of subpopulations. The second definition aims at precluding even more general forms of discrimination; this notion of evidence-consistency requires that the ranking must be justified on the basis of consistency with the expectations for every set in the collection C. Somewhat surprisingly, while evidence-consistency is a strictly stronger notion than domination-compatibility when the collection C is predefined, the two notions are equivalent when the collection C may depend on the ranking in question.

Details

STOC Conference 2018 Conference Paper

Composable and versatile privacy via truncated CDP

  • Mark Bun
  • Cynthia Dwork
  • Guy N. Rothblum
  • Thomas Steinke 0002

We propose truncated concentrated differential privacy (tCDP), a refinement of differential privacy and of concentrated differential privacy. This new definition provides robust and efficient composition guarantees, supports powerful algorithmic techniques such as privacy amplification via sub-sampling, and enables more accurate statistical analyses. In particular, we show a central task for which the new definition enables exponential accuracy improvement.

Details

NeurIPS Conference 2015 Conference Paper

Generalization in Adaptive Data Analysis and Holdout Reuse

  • Cynthia Dwork
  • Vitaly Feldman
  • Moritz Hardt
  • Toni Pitassi
  • Omer Reingold
  • Aaron Roth

Overfitting is the bane of data analysts, even when data are plentiful. Formal approaches to understanding this problem focus on statistical inference and generalization of individual analysis procedures. Yet the practice of data analysis is an inherently interactive and adaptive process: new analyses and hypotheses are proposed after seeing the results of previous ones, parameters are tuned on the basis of obtained results, and datasets are shared and reused. An investigation of this gap has recently been initiated by the authors in (Dwork et al. , 2014), where we focused on the problem of estimating expectations of adaptively chosen functions. In this paper, we give a simple and practical method for reusing a holdout (or testing) set to validate the accuracy of hypotheses produced by a learning algorithm operating on a training set. Reusing a holdout set adaptively multiple times can easily lead to overfitting to the holdout set itself. We give an algorithm that enables the validation of a large number of adaptively chosen hypotheses, while provably avoiding overfitting. We illustrate the advantages of our algorithm over the standard use of the holdout set via a simple synthetic experiment. We also formalize and address the general problem of data reuse in adaptive data analysis. We show how the differential-privacy based approach in (Dwork et al. , 2014) is applicable much more broadly to adaptive data analysis. We then show that a simple approach based on description length can also be used to give guarantees of statistical validity in adaptive settings. Finally, we demonstrate that these incomparable approaches can be unified via the notion of approximate max-information that we introduce. This, in particular, allows the preservation of statistical validity guarantees even when an analyst adaptively composes algorithms which have guarantees based on either of the two approaches.

PDF Details

STOC Conference 2015 Conference Paper

Preserving Statistical Validity in Adaptive Data Analysis

  • Cynthia Dwork
  • Vitaly Feldman
  • Moritz Hardt
  • Toniann Pitassi
  • Omer Reingold
  • Aaron Roth 0001

A great deal of effort has been devoted to reducing the risk of spurious scientific discoveries, from the use of sophisticated validation techniques, to deep statistical methods for controlling the false discovery rate in multiple hypothesis testing. However, there is a fundamental disconnect between the theoretical results and the practice of data analysis: the theory of statistical inference assumes a fixed collection of hypotheses to be tested, or learning algorithms to be applied, selected non-adaptively before the data are gathered, whereas in practice data is shared and reused with hypotheses and new analyses being generated on the basis of data exploration and the outcomes of previous analyses. In this work we initiate a principled study of how to guarantee the validity of statistical inference in adaptive data analysis. As an instance of this problem, we propose and investigate the question of estimating the expectations of m adaptively chosen functions on an unknown distribution given n random samples. We show that, surprisingly, there is a way to estimate an exponential in n number of expectations accurately even if the functions are chosen adaptively. This gives an exponential improvement over standard empirical estimators that are limited to a linear number of estimates. Our result follows from a general technique that counter-intuitively involves actively perturbing and coordinating the estimates, using techniques developed for privacy preservation. We give additional applications of this technique to our question.

Details

FOCS Conference 2015 Conference Paper

Robust Traceability from Trace Amounts

  • Cynthia Dwork
  • Adam Smith 0006
  • Thomas Steinke 0002
  • Jonathan R. Ullman
  • Salil P. Vadhan

The privacy risks inherent in the release of a large number of summary statistics were illustrated by Homer et al. (PLoS Genetics, 2008), who considered the case of 1-way marginals of SNP allele frequencies obtained in a genome-wide association study: Given a large number of minor allele frequencies from a case group of individuals diagnosed with a particular disease, together with the genomic data of a single target individual and statistics from a sizable reference dataset independently drawn from the same population, an attacker can determine with high confidence whether or not the target is in the case group. In this work we describe and analyze a simple attack that succeeds even if the summary statistics are significantly distorted, whether due to measurement error or noise intentionally introduced to protect privacy. Our attack only requires that the vector of distorted summary statistics is close to the vector of true marginals in ℓ 1 norm. Moreover, the reference pool required by previous attacks can be replaced by a single sample drawn from the underlying population. The new attack, which is not specific to genomics and which handles Gaussian as well as Bernouilli data, significantly generalizes recent lower bounds on the noise needed to ensure differential privacy (Bun, Ullman, and Vadhan, STOC 2014, Steinke and Ullman, 2015), obviating the need for the attacker to control the exact distribution of the data.

Details

ICML Conference 2013 Conference Paper

Learning Fair Representations

  • Richard S. Zemel
  • Yu Wu
  • Kevin Swersky
  • Toniann Pitassi
  • Cynthia Dwork

We propose a learning algorithm for fair classification that achieves both group fairness (the proportion of members in a protected group receiving positive classification is identical to the proportion in the population as a whole), and individual fairness (similar individuals should be treated similarly). We formulate fairness as an optimization problem of finding a good representation of the data with two competing goals: to encode the data as well as possible, while simultaneously obfuscating any information about membership in the protected group. We show positive results of our algorithm relative to other known techniques, on three datasets. Moreover, we demonstrate several advantages to our approach. First, our intermediate representation can be used for other classification tasks (i. e. , transfer learning is possible); secondly, we take a step toward learning a distance metric which can find important dimensions of the data for classification.

Details

FOCS Conference 2012 Conference Paper

The Privacy of the Analyst and the Power of the State

  • Cynthia Dwork
  • Moni Naor
  • Salil P. Vadhan

We initiate the study of "privacy for the analyst" in differentially private data analysis. That is, not only will we be concerned with ensuring differential privacy for the data (i. e. individuals or customers), which are the usual concern of differential privacy, but we also consider (differential) privacy for the set of queries posed by each data analyst. The goal is to achieve privacy with respect to other analysts, or users of the system. This problem arises only in the context of stateful privacy mechanisms, in which the responses to queries depend on other queries posed (a recent wave of results in the area utilized cleverly coordinated noise and state in order to allow answering privately hugely many queries). We argue that the problem is real by proving an exponential gap between the number of queries that can be answered (with non-trivial error) by stateless and stateful differentially private mechanisms. We then give a stateful algorithm for differentially private data analysis that also ensures differential privacy for the analyst and can answer exponentially many queries.

Details

FOCS Conference 2011 Conference Paper

The Promise of Differential Privacy: A Tutorial on Algorithmic Techniques

  • Cynthia Dwork

Differential privacy describes a promise, made by a data curator to a data subject: you will not be affected, adversely or otherwise, by allowing your data to be used in any study, no matter what other studies, data sets, or information from other sources is available. At their best, differentially private database mechanisms can make confidential data widely available for accurate data analysis, without resorting to data clean rooms, institutional review boards, data usage agreements, restricted views, or data protection plans. To enjoy the fruits of the research described in this tutorial, the data analyst must accept that raw data can never be accessed directly and that eventually data utility is consumed: overly accurate answers to too many questions will destroy privacy. The goal of algorithmic research on differential privacy is to postpone this inevitability as long as possible.

Details

FOCS Conference 2010 Conference Paper

Boosting and Differential Privacy

  • Cynthia Dwork
  • Guy N. Rothblum
  • Salil P. Vadhan

Boosting is a general method for improving the accuracy of learning algorithms. We use boosting to construct improved privacy-pre serving synopses of an input database. These are data structures that yield, for a given set Q of queries over an input database, reasonably accurate estimates of the responses to every query in Q, even when the number of queries is much larger than the number of rows in the database. Given a base synopsis generator that takes a distribution on Q and produces a "weak" synopsis that yields "good" answers for a majority of the weight in Q, our Boosting for Queries algorithm obtains a synopsis that is good for all of Q. We ensure privacy for the rows of the database, but the boosting is performed on the queries. We also provide the first synopsis generators for arbitrary sets of arbitrary low-sensitivity queries, i. e. , queries whose answers do not vary much under the addition or deletion of a single row. In the execution of our algorithm certain tasks, each incurring some privacy loss, are performed many times. To analyze the cumulative privacy loss, we obtain an O(ε 2 ) bound on the expected privacy loss from a single e-differentially private mechanism. Combining this with evolution of confidence arguments from the literature, we get stronger bounds on the expected cumulative privacy loss due to multiple mechanisms, each of which provides e-differential privacy or one of its relaxations, and each of which operates on (potentially) different, adaptively chosen, databases.

Details

SODA Conference 2010 Conference Paper

Differential Privacy in New Settings

  • Cynthia Dwork

Differential privacy is a recent notion of privacy tailored to the problem of statistical disclosure control: how to release statistical information about a set of people without compromising the the privacy of any individual [7]. We describe new work [10, 9] that extends differentially private data analysis beyond the traditional setting of a trusted curator operating, in perfect isolation, on a static dataset. We ask How can we guarantee differential privacy, even against an adversary that has access to the algorithm's internal state, eg, by subpoena? An algorithm that achives this is said to be pan-private. How can we guarantee differential privacy when the algorithm must continually produce outputs? We call this differential privacy under continual observation. We also consider these requirements in conjunction.

Details

STOC Conference 2009 Conference Paper

Differential privacy and robust statistics

  • Cynthia Dwork
  • Jing Lei

We show by means of several examples that robust statistical estimators present an excellent starting point for differentially private estimators. Our algorithms use a new paradigm for differentially private mechanisms, which we call Propose-Test-Release (PTR), and for which we give a formal definition and general composition theorems.

Details

STOC Conference 2007 Conference Paper

The price of privacy and the limits of LP decoding

  • Cynthia Dwork
  • Frank McSherry
  • Kunal Talwar

This work is at theintersection of two lines of research. One line, initiated by Dinurand Nissim, investigates the price, in accuracy, of protecting privacy in a statistical database. The second, growing from an extensive literature on compressed sensing (see in particular the work of Donoho and collaborators [4,7,13,11])and explicitly connected to error-correcting codes by Candès and Tao ([4]; see also [5,3]), is in the use of linearprogramming for error correction. Our principal result is the discovery of a sharp threshhold ρ*∠ 0.239, so that if ρ < ρ* and A is a random m x n encoding matrix of independently chosen standardGaussians, where m = O(n), then with overwhelming probability overchoice of A , for all x ∈ R n , LP decoding corrects ⌊ ρ m⌋ arbitrary errors in the encoding Ax, while decoding can be made to fail if the error rate exceeds ρ*. Our boundresolves an open question of Candès, Rudelson, Tao, and Vershyin [3] and (oddly, but explicably) refutesempirical conclusions of Donoho [11] and Candès et al [3]. By scaling and rounding we can easilytransform these results to obtain polynomial-time decodable random linear codes with polynomial-sized alphabets tolerating any ρ < ρ* ∠ 0.239 fraction of arbitrary errors. In the context of privacy-preserving datamining our results say thatany privacy mechanism, interactive or non-interactive, providingreasonably accurate answers to a 0.761 fraction of randomly generated weighted subset sum queries, and arbitrary answers on the remaining 0.239 fraction, is blatantly non-private.

Details

UAI Conference 2005 Conference Paper

On Privacy-Preserving Histograms

  • Shuchi Chawla 0001
  • Cynthia Dwork
  • Frank McSherry
  • Kunal Talwar

We advance the approach initiated by Chawla et al. for sanitizing (census) data so as to preserve the privacy of respondents while simultaneously extracting "useful" statistical information. First, we extend the scope of their techniques to a broad and rich class of distributions, specifically, mixtures of highdimensional balls, spheres, Gaussians, and other "nice" distributions. Second, we randomize the histogram constructions to preserve spatial characteristics of the data, allowing us to approximate various quantities of interest, e.g., cost of the minimum spanning tree on the data, in a privacy-preserving fashion.

Details

FOCS Conference 2000 Conference Paper

Zaps and Their Applications

  • Cynthia Dwork
  • Moni Naor

A zap is a two-round, witness-indistinguishable protocol in which the first round, consisting of a message from the verifier to the prover, can be fixed "once-and-for-all" and applied to any instance, and where the verifier does not use any private coins. We present a zap for every language in NP, based on the existence of non-interactive zero-knowledge proofs in the shared random string model. The zap is in the standard model, and hence requires no common guaranteed random string. We introduce and construct verifiable pseudo-random bit generators (VPRGs), and give a complete existential characterization of both noninteractive zero-knowledge proofs and zaps in terms of approximate VPRGs. We present several applications for zaps; In the timing model of C. Dwork et al. (1998) and using moderately hard functions, we obtain 3-round concurrent zero knowledge and 2-round concurrent deniable authentication (the latter protocol also operates in the resettable model of R. Canetti et al. (2000)). In the standard model we obtain 2-round oblivious transfer using public keys (3-round otherwise). We note that any zap yields resettable 2-round witness-indistinguishability and obtain a 3-round timing-based resettable zero-knowledge argument system for any language in NP.

Details

FOCS Conference 1999 Conference Paper

Magic Functions

  • Cynthia Dwork
  • Moni Naor
  • Omer Reingold
  • Larry J. Stockmeyer

In this paper we show that three apparently unrelated problems are in fact very closely related. We sketch these problems at a high level. The selective decommitment problem first arose in a slightly different form, selective decryption, in the context of Byzantine agreement, no later than 1985. Instead of seeing encryptions of plaintexts the adversary is given commitments to the plaintexts. This problem is poorly understood even in strong-receiver commitments, which leak no information about the plaintext values information-theoretically. The second problem is in complexity theory: what can be proved in (a possibly weakened form of) zero-knowledge in a 3-round argument (interactive proof in which the prover is polynomial-time bounded)? The Fiat-Shamir Methodology is cryptographic, and addresses a methodology suggested by Fiat and Shamir (1987) to construct a (non-interactive) signature scheme from any 3-round (not necessarily zero-knowledge) public-coin identification scheme.

Details

MFCS Conference 1997 Invited Paper

Positive Applications of Lattices to Cryptography

  • Cynthia Dwork

Abstract We describe constructions of several cryptographic primitives, including hash functions, public key cryptosystems, pseudo-random bit generators, and digital signatures, whose security depends on the assumed worst-case or average-case hardness of problems involving lattices.

Details

FOCS Conference 1994 Conference Paper

A Theory of Competitive Analysis for Distributed Algorithms

  • Miklós Ajtai
  • James Aspnes
  • Cynthia Dwork
  • Orli Waarts

We introduce a theory of competitive analysis for distributed algorithms. The first steps in this direction were made in the seminal papers of Y. Bartal et al. (1992), and of B. Awerbuch et al. (1992), in the context of data management and job scheduling. In these papers, as well as in other subsequent sequent work, the cost of a distributed algorithm is compared to the cost of an optimal global-control algorithm. In this paper we introduce a more refined notion of competitiveness for distributed algorithms, one that reflects the performance of distributed algorithms more accurately. In particular, our theory allows one to compare the cost of a distributed on-line algorithm to the cost of an optimal distributed algorithm. We demonstrate our method by studying the cooperative collect primitive, first abstracted by M. Saks, N. Shavit, and H. Woll (1991). We provide the first algorithms that allow processes to cooperate to finish their work in fewer steps. Specifically, we present two algorithms (with different strengths), and provide a competitive analysis for each one. >

Details

FOCS Conference 1990 Conference Paper

Perfectly Secure Message Transmission

  • Danny Dolev
  • Cynthia Dwork
  • Orli Waarts
  • Moti Yung

The problem of perfectly secure communication in a general network in which processors and communication lines may be faulty is studied. Lower bounds are obtained on the connectivity required for successful secure communication. Efficient algorithms that operate with this connectivity and rely on no complexity theoretic assumptions are derived. These are the first algorithms for secure communication in a general network to achieve simultaneously the goals of perfect secrecy, perfect resiliency, and a worst case time which is linear in the diameter of the network. >

Details

FOCS Conference 1989 Conference Paper

On the Power of 2-Way Probabilistic Finite State Automata (Extended Abstract)

  • Cynthia Dwork
  • Larry J. Stockmeyer

The recognition power of two-way probabilistic finite-state automata (2PFAs) is studied. It is shown that any 2PFA recognizing a nonregular language must use exponential expected time infinitely often. The power of interactive proof systems (IPSs) where the verifier is a 2PFA is also investigated. It is shown that (1) IPSs in which the verifier uses private randomization are strictly more powerful than IPSs in which the random choices of the verifier are made public to the prover. (2) IPSs in which the verifier uses public randomization are strictly more powerful than 2PFAs alone, that is, without a prover; (3) every language accepted by some deterministic Turing machine in exponential time can be accepted by some IPS. Other results concern IPSs with 2PFA verifiers that run in polynomial expected time. >

Details

FOCS Conference 1986 Conference Paper

Flipping Persuasively in Constant Expected Time (Preliminary Version)

  • Cynthia Dwork
  • David B. Shmoys
  • Larry J. Stockmeyer

We present a distributed protocol for achieving a distributed coin in the presence of an extremely powerful adversary in constant time. The protocol can tolerate up to n/log n malicious processor failures where n is the number of processors in the system. The protocol needs only a fixed constant number of rounds of message exchange; no preprocessing is required. As a corollary we obtain an (n/log n)-resilient probabilistic protocol for Byzantine agreement running in constant expected time. Combining this with a generalization of a technique of Bracha, we obtain a probabilistic Byzantine agreement protocol tolerant of almost n/3 failures with O(log log n) expected running time.

Details

TARK Conference 1986 Conference Paper

Knowledge and Common Knowledge in a Byzantine Environment I: Crash Failures

  • Cynthia Dwork
  • Yoram Moses

By analyzing the states of knowledge that the processors attain in an unreliable system of asimple type, we capture some of the basic underlying structure of such systems. The analysis provides us with a better understanding of existing protocols for problems such as Byzantine agreement, generalizes them considerably, and facilitates the design of improved protocols for many related problems.

Details

FOCS Conference 1983 Conference Paper

On the Minimal Synchronism Needed for Distributed Consensus

  • Danny Dolev
  • Cynthia Dwork
  • Larry J. Stockmeyer

Reaching agreement is a primitive of distributed computing. While this poses no problem in an ideal, failure-free environment, it imposes certain constraints on the capabilities of an actual system: a system is viable only if it permits the existence of consensus protocols tolerant to some number of failures. Fischer, Lynch and Paterson [FLP] have shown that in a completely asynchronous model, even one failure cannot be tolerated. In this paper we extend their work, identifying several critical system parameters, including various synchronicity conditions, and examine how varying these affects the number of faults which can be tolerated. Our proofs expose general heuristic principles that explain why consensus is possible in certain models but not possible in others.

Details