ITA coincided with NetCod07, which was a small miniworkshop (single-day, single-track) on network coding. I went to a few talks there, but unfortunately missed the one I most wanted to see, “Resilient network coding in the presence of Byzantine adversaries.” Oh well, at least there’s a paper for me to read.
- The benefits of network coding for peer-to-peer storage systems (Alexandros G. Dimakis, P. Brighten Godfrey, Martin J. Wainwright, Kannan Ramchandran, UC Berkeley)
This talk was on designing a decentralized storage system in which individual nodes (peers) hold coded chunks of the total file. To be concrete, say we have a 8 MB file. Someone wishing to download the file can download the 8 chunks of 1 MB each from randomly chosen peers and with high probability recover the file. The issue with this system is that if a peer leaves the network and a new peer joins, that peer should not have to download all 8 MB to make a new coded 1 MB chunk for itself to store. So the question this paper answers is how much overhead (excess downloading) a new peer has to pay in order to store a coded packet, and how can we design codes whose overhead is low in terms of this metric so that peers can leave and join the network and still have the whole file stored. Alex calls these “regenerating codes,” which sounds kind of sci-fi to me.
- Code construction for two source interference (Elona Erez and Meir Feder, Tel Aviv University)
This paper looked at non-multicast network coding, and was focused on coming up with decentralized and low-complexity algorithms for accomplishing this. The approach was to make a “quasiflow” and use a modified version of a multicommodity flow algorithm to construct the quasiflow.
- Characaterizations of network error correction/detection and erasure correction (Shenghao Yang and Raymond W. Yeung, The Chinese University of Hong Kong)
This was a real big-picture talk, in which Prof. Yeung tried to argue that network coding has all the analogues of regular error correcting codes. In this sense, network coding is a generalization of algebraic coding. So there are analogies to the Singleton bound, and all sort of other things. In particular, minimum distance has a analogy in network coding, which can make a lot of intuitive connections clear.