  We study large-scale distributed cooperative systems that use optimistic
replication. We represent a system as a graph of actions (operations) connected
by edges that reify semantic constraints between actions. Constraint types
include conflict, execution order, dependence, and atomicity. The local state
is some schedule that conforms to the constraints; because of conflicts, client
state is only tentative. For consistency, site schedules should converge; we
designed a decentralised, asynchronous commitment protocol. Each client makes a
proposal, reflecting its tentative and{\slash}or preferred schedules. Our
protocol distributes the proposals, which it decomposes into
semantically-meaningful units called candidates, and runs an election between
comparable candidates. A candidate wins when it receives a majority or a
plurality. The protocol is fully asynchronous: each site executes its tentative
schedule independently, and determines locally when a candidate has won an
election. The committed schedule is as close as possible to the preferences
expressed by clients.
