UMBC CSEE Colloquium
Local Thresholding for Structured and Unstructured Graphs
Dr. Ran Wolff, Haifa University, Israel
2:00pm Friday, 28 September 2012, ITE 325B
note unusual time and room
Local thresholding algorithms were first offered a decade ago as a communication thrifty alternative for computation in large distributed environments. Their disadvantage, however, has always been in their brittleness. A single cycle in the communication graph could mean the algorithm converges to the wrong value. This talk describes two advances in local thresholding algorithms which overcome the demand for cycle freedom. The first is a local tree induction protocol for structured peer-to-peer networks which seamlessly integrates with the local thresholding algorithm. The second are new local stopping and update rules which permit execution of the local thresholding algorithm on general graphs. The first solution vastly outperforms a gossip based algorithm on simple computation tasks in a Chord-like peer-to-peer network. The second may transform the way data is processed in wireless sensor networks, where gossip is mostly considered impermissibly costly.