Propagation of authorizations in distributed database systems

ABSTRACT

We consider the propagation of authorizations in distributed database systems. If no constraints are imposed on the propagation of authorization changes, then the authorization states at different sites may evolve inconsistently. A standard solution is to suppress the distributed aspect and make all changes appear as if they had occurred in some serial order at a single site, perhaps via an atomic commit protocol. However, rigid insistence on consistency may result in authorization changes being needlessly delayed, a problem exacerbated in the context of site or communication failures. We propose an optimistic authorization propagation algorithm. We specify an authorization table and a set of operations for altering the authorization table. Each site maintains a log of authorization operations. We exploit the semantics of authorization operations to avoid relying on an undo-redo mechanism for processing out of order operations. Instead we give efficient, direct algorithms to scan the log and update the authorization table. Any inconsistencies in replicas of the authorization table are transient and are eliminated by further communication between sites. We discuss pruning the authorization log.

REFERENCES

• BHG87: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• BL76: D.E. Bell and L.J. LaPadula. Secure computer systems: Unified exposition and multics interpretation. Technical Report MTR- 2997, The Mitre Corporation, Bedford, MA, March 1976.
• BLNS82: Andrew D. Birrell , Roy Levin , Michael D. Schroeder , Roger M. Needham, Grapevine: an exercise in distributed computing, Communications of the ACM, v.25 n.4, p.260-274, April 1982 [doi>10.1145/358468.358487]
• DGH+87: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• DGMS85: Susan B. Davidson , Hector Garcia-Molina , Dale Skeen, Consistency in a partitioned network: a survey, ACM Computing Surveys (CSUR), v.17 n.3, p.341-370, Sept. 1985 [doi>10.1145/5505.5508]
• DoD85: DoD Computer Security Center. Trusted Computer System Evaluation Criteria, December 1985. DoD 5200.28-STD.
• Fag78: Ronald Fagin, On an authorization mechanism, ACM Transactions on Database Systems (TODS), v.3 n.3, p.310-319, Sept. 1978 [doi>10.1145/320263.320288]
• FM82: Michael J. Fischer , Alan Michael, Sacrificing serializability to attain high availability of data in an unreliable network, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588124]
• GW76: Patricia P. Griffiths , Bradford W. Wade, An authorization mechanism for a relational database system, ACM Transactions on Database Systems (TODS), v.1 n.3, p.242-255, Sept. 1976 [doi>10.1145/320473.320482]
• HW88: Maurice P. Herlihy , William E. Weihl, Hybrid concurrency control for abstract data types, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.201-210, March 1988, Austin, Texas, United States [doi>10.1145/308386.308440]
• JM90: S. Jajodia , David Mutchler, Dynamic voting algorithms for maintaining the consistency of a replicated database, ACM Transactions on Database Systems (TODS), v.15 n.2, p.230-280, June 1990 [doi>10.1145/78922.78926]
• Lam78: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• Lam86: Butler W Lampson, Designing a global name service, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.1-10, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10591]
• LLSG92: Rivka Ladin , Barbara Liskov , Liuba Shrira , Sanjay Ghemawat, Providing high availability using lazy replication, ACM Transactions on Computer Systems (TOCS), v.10 n.4, p.360-391, Nov. 1992 [doi>10.1145/138873.138877]
• Ng89: Tony P. Ng, Using histories to implement atomic objects, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.360-393, Nov. 1989 [doi>10.1145/75104.75106]
• SAJ94: P. Samarati, P. Ammann, and S. Jajodia. Propagation of authorizations in distributed database systems. (extended version), in preparation, 1994.
• SY85: Rob Strom , Shaula Yemini, Optimistic recovery in distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.3, p.204-226, Aug. 1985 [doi>10.1145/3959.3962]
• WB84: Gene T.J. Wuu , Arthur J. Bernstein, Efficient solutions to the replicated log and dictionary problems, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.233-242, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806750]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases

  D. Software
  D.4 OPERATING SYSTEMS

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General
          Subjects: Security, integrity, and protection**

General Terms:
Algorithms, Theory