SIGACT Distributed Computing News
November 14, 2012, 3:53 pm
Filed under: Uncategorized | Tags: ,

From Idit Keidar

Two new SIGACT News Distributed Computing columns are now online.

The September column features a tutorial on distributed Computability:

“Computability in Distributed Computing: a Tutorial”
by Maurice Herlihy, Sergio Rajsbaum, and Michel Raynal.

The forthcoming (December) column reviews distributed computing events
in 2012. Specifically:

– “Transactional Memory: Beyond the First Two Decades”
(Dijkstra Award acceptance speech) by Maurice Herlihy and Nir Shavit

– “Principles of Distributed Computing Doctoral Dissertation Award”

– Review of PODC 2012 by Siddhartha Sen

– Review of DISC 2012 by Mika Goos

– Review of WTTM 2012 by Vincent Gramoli and Alessia Milani

As always, the columns are available online, both at the Technion:

and at MIT:


Dense Subgraphs on Dynamic Networks
November 5, 2012, 10:17 pm
Filed under: Uncategorized | Tags: , ,

A quick pointer to an interview with my former student Amitabh Trehan on his DISC paper “Dense Subgraphs on Dynamic Networks” .

This is a neat result in the dynamic graph setting where an adversary can add and delete edges in a graph, but the number of nodes is always fixed at n.  One of their results is as follows.  In the case where the maximum number of rounds that it takes a message to traverse the network is always polylog, they give a polylog time algorithm that allows each node to approximate within a constant factor the densest subgraph.  This is in the CONGEST model where in each round, each node can send an O(log n) bit message to each neighbor.