Bounded Ignorance in Replicated Systems

Summary: Proposes N-ignorant transactions: each transaction may be unaware of results from up to N prior transactions, trading bounded integrity-constraint violations for up to N+1× higher concurrency versus serializability. Presents algorithms and state-space methods to compute worst-case reachable violations for a given N. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 924
Venue: PODS
Year: 1991
Pagerank: 6.9633182e-05
Overall Rank: 4,006 | 72.52%
DOI: 10.1145/113413.113419

Incoming Non-self Citations Over Time

Authors

1. Narayanan Krishnakumar (State University of New York at Stony Brook)
2. Arthur J. Bernstein (State University of New York at Stony Brook)

BibTeX Citation

@inproceedings{krishnakumar_pods91,
        address = {New York, NY, USA},
        series = {{PODS} '91},
        title = {{Bounded Ignorance in Replicated Systems}},
        url = {https://dl.acm.org/doi/10.1145/113413.113419},
        doi = {10.1145/113413.113419},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Krishnakumar, Narayanan and Bernstein, Arthur J.},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,676	Efficient Numerical Error Bounding for Replicated Network Services	2000	VLDB	8.2705376e-05
4,227	Distributed Algorithms For Dynamic Replication Of Data	1992	PODS	6.8208686e-05
5,049	Cache-and-Query for Wide Area Sensor Databases	2003	SIGMOD	6.3868781e-05
13,091	High Throughput Escrow Algorithms for Replicated Databases (Extended Abstract)	1992	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,189	Sacrificing Serializability to Attain High Availability of Data in an Unreliable Network	1982	PODS	0.00011749508
2,450	Formal Model of Correctness Without Serializability	1988	SIGMOD	8.565918e-05
2,591	Knowledge-based Integrity Constraint Validation	1986	VLDB	8.366058e-05
2,835	A Formal Approach to Recovery by Compensating Transactions	1990	VLDB	8.0726749e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	14,433	The Group Paradigm for Concurrency Control Protocols (Extended Abstract)	1988	SIGMOD
2	13,021	Relative Serializability: An Approach for Relaxing the Atomicity of Transactions	1994	PODS
3	766	The Case for Determinism in Database Systems	2010	VLDB
4	13,034	A Transaction Replication Scheme for a Replicated Database with Node Autonomy	1994	VLDB
5	5,578	Relaxed Currency Serializability for Middle-Tier Caching and Replication	2006	SIGMOD
6	5,910	Replication, Consistency, and Practicality: Are These Mutually Exclusive?	1998	SIGMOD
7	5,934	Semantics Based Transaction Management Techniques for Replicated Data	1988	SIGMOD
8	14,412	Concurrency Control In Multilevel-Secure Databases Based On Replicated Architecture	1990	SIGMOD
9	9,097	On Correctness of Non-serializable Executions	1993	PODS
10	9,025	Tolerating Bounded Inconsistency for Increasing Concurrency in Database Systems	1992	PODS