Allowing a set of objects to make a consistent decision, according to the values they propose, is a fundamental problem of distributed systems. When the system is reliable and synchronous the problem is simple. In the context of unreliable asynchronous systems that have to meet real-time constraints, the problem is far from trivial. A negative result stipulates that it is impossible to design a consensus protocol even if only one object crashes. The author considers timed asynchronous systems. He first proposes a general definition for decision-with-deadlines problems and then designs a protocol that solves these problems in timed asynchronous systems. An object can vote a or b. In a "good" configuration (there are not too many crashes and messages are timely) objects will decide consistently A or B according to the number of votes a or b that they have received. A and B are incompatible decision values. If there are too many crashes or too many messages that are not timely then it is possible that an object decides E (exception). Timed atomic commitment constitutes a particular instantiation of this problem.
展开▼
