k-agreement: The set D of decision values has cardinality at most k.While the notion of Limited Bureaucracy remains the same, Non Triviality is generalized in the obvious way: if xp=v for all p then, dq=v for every correct process q. Give a (k-1)-resilient protocol for k-agreement.
COMMUTATIVITY LEMMA. Let S and R be two disjoint sets of processes and let and be two runs of events where only processes in, respectively, S and R take steps. Then, for any configuration C, .Does the same lemma hold for synchronous systems?
Show that given a (c(n),d(n))-decomposition it is possible to compute a maximal independent set in O(c(n) d(n)) rounds in the distributed model of computation.