Bernadette Charron-Bost, Fabrice Le Fessant: Validity Conditions in Agreement Problems and Time Complexity. SOFSEM 2004: 196-207