Singing a MIS

Sandy Irani, Michael Luby

We introduce a broadcast model called the singing model, where agents are oblivious of the size and structure of the communication network, even their immediate neighborhood. Agent…