Machinations

I should sell this pic to the Canadan government, or to the Calgarians!

A riveting talk was the keynote  given by Bruce Hendrickson:`Emerging Challenges and Opportunities in Parallel computing: The Cretaceous Redux?’.  He discussed the state of parallel computing and the wide gap between theory and practice in the area.  With the advancement of Moore’s law and new technologies like multi-core emerging, a revolutionary change of environment is upon us and many  present technologies in practice like MPI may face extinction. He compared it to the Cretaceous era with the well adapted and highly specialized Dinosaurs about to feel the meteors come plummeting through the atmosphere. Upon some rocks, there scurry about scruffy rodents, the people in theory, oblivious to reality and immune in some ways to the incoming meteors. This change would thrust upon the rodents the task of rebuilding the world, moving the dead bodies of the dinosaurs out of the way. All in all, great opportunities await in this scenario for both the theoretician and the practitioner.

George Giakkoupis presented The Effect of Power-Law Degrees on the navigability of Small Worlds, his work with Pierre Fraigniaud. This work has a somewhat surprising extension to Kleinberg’s famous results on small world networks . The Kleinberg model  has a n-node d-dimensional lattice where each node u has directed edges to it’s closest neighbors plus a long range link with target chosen among all nodes v with probability proportional to 1/d(u,v)^r where d(u,v) is the distance between the node u and node v.  Kleinberg showed that when r=d (the dimension of the lattice), greedy search needs O(log^2 n) expected steps to locate a target from a source.  In contrast, for r not equal to d, any decentralized algorithm will need  polynomial(n) expected steps. This showed that in a small world network, not only is the diameter small but there is a way to find paths in a decentralized way, provided each agent has a sense of direction. George and Pierre modified the Kleinberg model so that the number of long range links follows a power-law distribution. They discovered that power-laws help navigation iff 2 < a < 3, where a is the exponent of the  power law.  In particular, they showed that greedy search requiring O(log^(a-1)n) steps for a in such a range.  The effect of the power-law distribution is significant: As a approaches 2 from above, the expected number of steps of greedy routing in the augmented lattice with power-law degrees approaches the square-root of the expected number of steps of greedy routing in the augmented lattice with fixed degrees, even with both networks having the same average degree. The other surprising thing is that their results don’t seem to depend on the dimensionality of the lattice.

A short note on two other papers. Chen Avin et al’s paper SINR Diagrams: Towards Algorithmically Usable SINR Models of Wireless Networks (presented by Yuval Emek) discusses the properties of the Signal-to-Interference and Noise Ratio (SINR) model which seems to be a more realistic alternative to simpler models such as Unit Disk Graph (UDG).  Their model allows for the possible convexity of  reception zones which seems to be observed in practice.   Prosenjit Bose, Paz Carmi and Stephane Durocher’s Bounding the Locality of Distributed Routing Algorithms (presented by Durocher) discusses various parameters necessary and/or sufficient to permit local routing on a network modelled by a connected undirected graph, and establish bounds on locality of routing for these parameters, as well as bounds on dilation (worst-case ratio of actual route lengths to shortest path lengths).

… and that’s all from PODC.