{"id":65,"date":"2011-03-30T14:18:00","date_gmt":"2011-03-30T14:18:00","guid":{"rendered":"http:\/\/www.syslog.cl.cam.ac.uk\/?p=65"},"modified":"2011-04-04T00:02:34","modified_gmt":"2011-04-04T00:02:34","slug":"4th-winter-school-in-hot-topics-in-distributed-computing","status":"publish","type":"post","link":"https:\/\/www.syslog.cl.cam.ac.uk\/2011\/03\/30\/4th-winter-school-in-hot-topics-in-distributed-computing\/","title":{"rendered":"4th Winter School in Hot Topics in Distributed Computing"},"content":{"rendered":"

Last week I attended the 4th Winter School in Hot Topic in Distributed Computing<\/a> organised by INRIA. The winter school was located in La Plagne (a classic ski resort in the French Alps) so good food and astonishing landscapes were guaranteed.<\/p>\n

The winter school program was structured in 2 sessions per day. This year, the invited researchers were Shafi Goldwasser<\/a> from MIT, Timothy Roscoe<\/a> from ETH Zurich, Nir Shavit<\/a> from Oracle and Tel Aviv University, Luis Rodrigues<\/a> from INESC-ID, Andr\u00c3\u00a9 Seznec<\/a> from INRIA, Pablo Rodr\u00c3\u00adguez<\/a> from Telef\u00c3\u00b3nica Research and Serge Abitebou<\/a> from INRIA. The talks covered different topics of distributed computing and the slides might be available soon in the winter school website. Nevertheless, I strongly recommend checking the webpage of each speaker for further details about their work. In addition to these sessions, two doctoral sessions allowed\u00c2\u00a0 PhD students to show their work and to get some valuable feedback.<\/p>\n


\nThe first session was by Shafi Goldwasser about \"Secrets and Proofs\", or in other words, how cryptography and interactive proofs can be used to make more secure distributed computing systems. She explained the concepts behind secure multi-party computation and some considerations that must be taken into account for resource-limited devices such as sensors.<\/p>\n

Timothy Roscoe described the design considerations behind an OS suitable for multi-core machines that led his group to design and implement Barrelfish<\/a> in collaboration with Microsoft Research. Barrelfish is a micro-kernel OS that uses message passing techniques instead of shared memory. Multi-core machines tend to look more like a network (see Intel's Single-chip cloud computer -SCC <\/a>, a microcosmos of cloud datacenters). However, as Roscoe said, despite adding more cores brings more cycles, memory and bus are the main bottlenecks in multi-core computers. More chips do not necessarily imply more off-chip bandwidth, more cache or more RAM capacity and in this kind of scenario, a monolithic OS presents scalability problems. Barrelfish solves this issue by using a distributed memory architecture (replicating the state at each core increases performance) and message passing. This technique reduces the latency compared to Shared Memory and it makes possible scaling to hundreds or thousands of cores.<\/p>\n

On Wednesday morning, Nir Shavit showed how Flat Combining<\/a> can be used to optimise data structures for parallelism. One of the main problems are locks: they make execution sequential. Moreover, being sophisticated in synchronisation can be counter-productive and it can cause a considerable memory overhead. Flat-combining uses a single thread to combine all the requests to the data structure from several threads thus improves the cache behaviour by reducing the number of cache misses. Moreover, Flat-combining requires little synchronisation and scales much better than systems based on locks. He described how this technique improves the performance of LIFO stacks, priority queues and hash tables (Nir introduced Hopscotch HasTables). In his opinion, in the future we will see data structures more randomised (hash tables, skiplists, randomised collections), relaxed (unordered pools instead of stacks and queues) and flat.<\/p>\n

In the afternoon, Luis Rodrigues highlighted the benefits of DSTM. He is currently involved on a european project called Transactional Memory in the Cloud<\/a>. In his talk, Rodrigues reviewed some case studies and he compared their performance. He show how a technique does not outperform the others because of its dependence on network latency. The use-cases he covered were:<\/p>\n