A method and computer program product for providing Global Attribute Uniqueness (GAU) using an Ordered Message Service (OMS) is presented. A database operation is received from a client. A determination is made regarding whether the operation changes a value to a current value and when the operation would change a value to a current value then operation is ended. When the operation would not change a value to a current value the operation is decomposed into ADD messages and DELETE messages. The ADD messages are sent to a GAU manager and GAU state is checked and updated. The updates are committed to GAU state and the Directory Server (DS) is updated. Operation is then returned to the client. DELETE messages are sent to the GAU manager and GAU state is updated. The updates are then committed.