Optimal Response Time Retrieval of Replicated Data

Summary: Reduce optimal access planning for retrieving sets of replicated pages to a network-flow formulation, yielding polynomial-time optimal disk-access schedules and extensions for heterogeneous/preloaded/distributed disks. Prove a universal worst-case response-time lower bound over all replication schemes, present a scheme that attains it, and show simulations where that scheme also substantially reduces average response time. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1013
Venue: PODS
Year: 1994
Pagerank: 5.093636e-05
Overall Rank: 13,017 | 10.70%
DOI: 10.1145/182591.182596

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Ling Tony Chen (Lawrence Berkeley National Laboratory)
2. Doron Rotem (Lawrence Berkeley National Laboratory)

BibTeX Citation

@inproceedings{chen_pods94,
        address = {New York, NY, USA},
        series = {{PODS} '94},
        title = {{Optimal Response Time Retrieval of Replicated Data}},
        url = {https://dl.acm.org/doi/10.1145/182591.182596},
        doi = {10.1145/182591.182596},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Chen, Ling Tony and Rotem, Doron},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
270	Disk Shadowing	1988	VLDB	0.00022768303
6,985	Disk Mirroring with Alternating Deferred Updates	1993	VLDB	5.7303405e-05
8,292	Declustering Objects for Visualization	1993	VLDB	5.4574671e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,256	File Allocation in Distributed Databases with Interaction between Files	1983	VLDB
2	3,807	Availability in Partitioned Replicated Databases (Extended Abstract)	1986	PODS
3	8,086	Load Balancing in a Locally Distributed Database System	1986	SIGMOD
4	13,754	Near-Optimal Dynamic Replication in Unstructured Peer-to-Peer Networks	2008	PODS
5	12,462	An Access Cost-Aware Approach for Object Retrieval over Multiple Sources	2010	VLDB
6	6,460	Reading a Set of Disk Pages	1993	VLDB
7	1,268	An Efficient, Fault-Tolerant Protocol For Replicated Data Management	1985	PODS
8	13,098	A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols	1991	PODS
9	13,874	Replicated Declustering of Spatial Data	2004	PODS
10	4,227	Distributed Algorithms For Dynamic Replication Of Data	1992	PODS