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: h51adcf6801351ea8
Venue: PODS
Year: 1991
Pagerank: 6.8094639e-05
Overall Rank: 4,096 | 72.47%
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,724	Efficient Numerical Error Bounding for Replicated Network Services	2000	VLDB	8.0923863e-05
4,298	Distributed Algorithms For Dynamic Replication Of Data	1992	PODS	6.6798849e-05
5,173	Cache-and-Query for Wide Area Sensor Databases	2003	SIGMOD	6.243639e-05
13,381	High Throughput Escrow Algorithms for Replicated Databases (Extended Abstract)	1992	VLDB	4.9793485e-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,214	Sacrificing Serializability to Attain High Availability of Data in an Unreliable Network	1982	PODS	0.00011493628
2,490	Formal Model of Correctness Without Serializability	1988	SIGMOD	8.3959371e-05
2,640	Knowledge-based Integrity Constraint Validation	1986	VLDB	8.1805168e-05
2,896	A Formal Approach to Recovery by Compensating Transactions	1990	VLDB	7.8921728e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,096	Reliable Scheduling of Database Transactions for Unreliable Systems	1984	PODS
2	13,311	Relative Serializability: An Approach for Relaxing the Atomicity of Transactions	1994	PODS
3	781	The Case for Determinism in Database Systems	2010	VLDB
4	13,324	A Transaction Replication Scheme for a Replicated Database with Node Autonomy	1994	VLDB
5	5,699	Relaxed Currency Serializability for Middle-Tier Caching and Replication	2006	SIGMOD
6	6,024	Replication, Consistency, and Practicality: Are These Mutually Exclusive?	1998	SIGMOD
7	6,050	Semantics Based Transaction Management Techniques for Replicated Data	1988	SIGMOD
8	14,723	Concurrency Control In Multilevel-Secure Databases Based On Replicated Architecture	1990	SIGMOD
9	9,270	On Correctness of Non-serializable Executions	1993	PODS
10	9,194	Tolerating Bounded Inconsistency for Increasing Concurrency in Database Systems	1992	PODS