loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02)
A Simple Algorithmic Characterization of Uniform Solvability
Vancouver, BC, Canada
November 16-November 19
ISBN: 0-7695-1822-2
Eli Gafni, University of California at Los Angeles
The Herlihy-Shavit (HS) conditions characterizing the solvability of asynchronous tasks over n processors have been a milestone in the development of the theory of distributed computing. Yet, they were of no help when researcher sought algorithms that do not depend on n.To help in this pursuit we investigate the uniform solvability of an infinite uniform sequence of tasks T0, T1, T2, …,where Ti is a task over processors p0, p1,…, pi , and Ti extends Ti - 1. We say that such a sequence is uniformly solvable if there exit protocols to solve each Ti and the protocol for Ti extends the protocol for Ti. This paper establishes that although each Ti may be solvable, the uniform sequence is not necessarily uniformly solvable. We show this by proposing a novel uniform sequence of solvable tasks and proving that the sequence is not amenable to a uniform solution. We then extend the HS conditions for a task over n processors, to uniform solvability in a natural way. The technique we use to accomplish this is to generalize the alternative algorithmic proof, by Borowsky and Gafni, of the HS conditions, by showing that the infinite uniform sequence of task of Immediate Snapshots is uniformly solvable. A side benefit of the technique is a widely applicable methodology for the development of uniform protocols.
Citation:
Eli Gafni, "A Simple Algorithmic Characterization of Uniform Solvability," focs, pp.228, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.