Loading...
Please wait, while we are loading the content...
Similar Documents
A Tight Lower Bound for Processor Coordination �
| Content Provider | Semantic Scholar |
|---|---|
| Author | Chaudhuri, Soma Herlihy, Maurice Lynch, Nancy A. |
| Copyright Year | 2005 |
| 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 rounds of communication for oblivious solutions that tolerate f failures This shows that there is an inherent trade o 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://www.markrtuttle.com/data/papers/chlt93-wrcs.pdf |
| Alternate Webpage(s) | http://www.markrtuttle.com/papers/chlt93-wrcs.pdf |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Central processing unit Contain (action) Sense of identity (observable entity) Solutions Time complexity |
| Content Type | Text |
| Resource Type | Article |
