A Tight Lower Bound for Processor Coordination Soma

Content Provider	Semantic Scholar
Author	Chaudhuriy Maurice Herlihyz Nancy, Ayodi Lynchy Mark, Rubinstein We, Tuttlez Abstract
Copyright Year	2010
Abstract	We prove a tight lower bound on the running time of oblivious solutions to k-set agreement. In k-set agreement, processors start with input values from a given set and choose output values from the same set. In every execution, the set of output values must be contained in the set of input values, and the set of output values must have size at most k. A solution is oblivious if it does not make use of processor identities. We analyze this problem in a synchronous model where processors can fail by just stopping. We prove a lower bound of bf =kc + 1 rounds of communication for oblivious solutions that tolerate f failures. This shows that there is an inherent trade-oo between the running time, the degree of coordination required, and the number of faults tolerated, even in idealized models like ours.
File Format	PDF HTM / HTML
Alternate Webpage(s)	http://groups.csail.mit.edu/tds/papers/Lynch/wrcs93.pdf
Language	English
Access Restriction	Open
Content Type	Text
Resource Type	Article