Matfilosofer är ett klassiskt schemaläggningsproblem för lokal ömsesidig uteslutning på godtyckliga konfliktdiagram. Vi skapar nödvändiga villkor för att lösa vänta-fri middag under eventuellt svag uteslutning i meddelande-passing system med krasch fel. Vänta-fri middag ser till att varje korrekt hungrig process så småningom äter. Eventuell svag uteslutning tillåter ändligt många schemaläggning misstag, men så småningom inga levande grannar äter samtidigt; detta uteslutningskriterium modellerar scenarier där schemaläggning misstag är återvinningsbara eller bara påverkar prestanda. Tidigare arbete visade att den så småningom perfekta feldetektorn (3P) är tillräcklig för att lösa väntefria måltider under eventuell svag uteslutning; vi bevisar att 3P också är nödvändigt, och därmed 3P är den svagaste oraklet för att lösa detta problem. Vår minskning slår också fast att alla sådana matlösningar kan göras så småningom rättvisa. Slutligen kan själva minskningen vara av mer allmänt intresse; när den tillämpas på vänta-fri evig svag uteslutning, ger vår minskning ett alternativt bevis på att det kraftfullare förtroende orakel (T ) är nödvändigt (men inte tillräckligt) för att lösa problemet med fel-tolerant ömsesidig uteslutning (FTME).
Det visas i REF att 3P är nödvändigt för att lösa denna variant av mat.
The weakest failure detector for wait-free dining under eventual weak exclusion
{'venue': "SPAA '09", 'journal': None, 'mag_field_of_study': ['Computer Science']}