* Faculty       * Staff       * Students & Alumni       * Committees       * Contact       * Institute Directory
* Undergraduate Program       * Graduate Program       * Courses       * Institute Catalog      
* Undergraduate       * Graduate       * Institute Admissions: Undergraduate | Graduate      
* Colloquia       * Seminars       * News       * Events       * Institute Events      
* Overview       * Lab Manual       * Institute Computing      
No Menu Selected

* News


Local Thresholding for Structured and Unstructured graphs

Speaker: Dr. Ran Wolff
Haifa University

October 11, 2012 - 4:00 p.m. to 5:00 p.m.
Location: SAGE 5101
Hosted By: Dr. Bolek Szymanski (x2714)


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.

Last updated: September 12, 2012