There are a number of shortest path algorithms. A good place to start whenever looking for parallel BSP algorithms is the old theory work on PRAM machines.
http://www.google.ca/search?sourceid=chrome&ie=UTF-8&q=pram+shortest+path+algorithm There are a few papers listed in the above search which would likely be an excellent starting point for a GSOC student. Thanks, Neal. On Wed, Mar 16, 2011 at 6:53 AM, Edward J. Yoon <[email protected]>wrote: > > So to conclude, I think it's a good idea to mention Bellman-Ford and give > > some resources about it without define it as mandatory (it's good to give > > students some freedom - it's motivating), then it's the role of the > mentor > > to guide the student to the right implementation and how the algorithm > can > > be applied to BSP. > > +1, I agree with you. > > Thanks for your comment and advice! > > On Wed, Mar 16, 2011 at 7:08 PM, Alois Cochard <[email protected]> > wrote: > > Since Bellman-Ford seems to be the only distributed shortest path finding > > algorithm to exist actually (is it correct ?), would be nice to point > > students to it. > > > > But I think it's must not be a 'mandatory point' if a student is capable > to > > come with his own distributed algorithm - we don't know, perhaps > > a genius student will come with this - we can accept it. > > > > For the majority of students, telling them to focus on Bellman-Ford is a > > good idea, making them able to think about implementation and > understanding > > Hama/BSP instead of breaking their heads by trying to find an original > > algorithm (or trying to make distributed a 'non-distributable' one) and > > loosing lot of time. > > > > I found a nice publication about history of Bellman-Ford / Distributed > > [Asynchronous] Bellman-Ford: > > http://www.walden-family.com/public/bf-history.pdf > > (fun to see that this algorithm is used by ARPANET for routing -didn't > know > > that- and how the algorithm evolved) > > > > So to conclude, I think it's a good idea to mention Bellman-Ford and give > > some resources about it without define it as mandatory (it's good to give > > students some freedom - it's motivating), then it's the role of the > mentor > > to guide the student to the right implementation and how the algorithm > can > > be applied to BSP. > > > > I'm more used to Dijkstra/A* than Bellman-Ford and still a newbee with > Hama > > but if you need help for mentorship (or as a backup mentor) don't > hesitate > > to ask, I have a strong interest for this kind of algorithms/problems and > > open to spend some of my free time on this. > > > > Cheers, > > > > > > On 15 March 2011 15:22, Edward J. Yoon <[email protected]> wrote: > > > >> Thanks. > >> > >> BTW, What do you think about the task topic? Students have to design > >> the scenario from A to Z. > >> > >> The task description should be detailed and informative? If so, it > >> seems better to focus on bellman-ford algorithm. > >> > >> On Tue, Mar 15, 2011 at 9:13 PM, Alois Cochard <[email protected] > > > >> wrote: > >> > Thanks a lot Eddie, everything is ok now :) > >> > > >> > The shortest path finding algorithm is a really a great project, if > was > >> > still a student I would loved working on this ! > >> > > >> > I hope that a passionate student will find interest in it ! > >> > > >> > Good luck ! > >> > > >> > -- > >> > *Alois Cochard* > >> > http://aloiscochard.blogspot.com > >> > http://twitter.com/aloiscochard > >> > > >> > On 15 March 2011 11:38, Edward J. Yoon <[email protected]> wrote: > >> > > >> >> > Even if not qualified for mentor-ship I wanted to take a look at > it, > >> but > >> >> the > >> >> > link don't work :( > >> >> > >> >> Sounds great! > >> >> > >> >> > "The selected filter with id '12315366' does not exist." > >> >> > > >> >> > Perhaps I haven't sufficient right in JIRA to see it ? > >> >> > >> >> Oh, .. I've just changed permission to everyone, Pls check again. > >> >> > >> >> Thanks. > >> >> > >> >> On Tue, Mar 15, 2011 at 7:30 PM, Alois Cochard < > [email protected] > >> > > >> >> wrote: > >> >> > Hello, > >> >> > > >> >> > Even if not qualified for mentor-ship I wanted to take a look at > it, > >> but > >> >> the > >> >> > link don't work :( > >> >> > > >> >> > "The selected filter with id '12315366' does not exist." > >> >> > > >> >> > Perhaps I haven't sufficient right in JIRA to see it ? > >> >> > > >> >> > Thanks, > >> >> > > >> >> > Alois Cochard > >> >> > http://aloiscochard.blogspot.com > >> >> > http://twitter.com/aloiscochard > >> >> > > >> >> > On 11 March 2011 02:06, Edward J. Yoon <[email protected]> > wrote: > >> >> > > >> >> >> Here's our gsoc tasks. > >> >> >> > >> >> >> http://s.apache.org/Hama-GSoC > >> >> >> > >> >> >> Who can participate in these issues as mentor? > >> >> >> > >> >> >> I can help for all issues as a mentor or a co-mentor. > >> >> >> > >> >> >> Thanks. > >> >> >> -- > >> >> >> Best Regards, Edward J. Yoon > >> >> >> http://blog.udanax.org > >> >> >> http://twitter.com/eddieyoon > >> >> >> > >> >> > > >> >> > >> >> > >> >> > >> >> -- > >> >> Best Regards, Edward J. Yoon > >> >> http://blog.udanax.org > >> >> http://twitter.com/eddieyoon > >> >> > >> > > >> > >> > >> > >> -- > >> Best Regards, Edward J. Yoon > >> http://blog.udanax.org > >> http://twitter.com/eddieyoon > >> > > > > > > > > -- > > *Alois Cochard* > > http://aloiscochard.blogspot.com > > http://twitter.com/aloiscochard > > > > > > -- > Best Regards, Edward J. Yoon > http://blog.udanax.org > http://twitter.com/eddieyoon >
