Machinations


Congratulations to Mahnush
January 15, 2016, 10:28 pm
Filed under: Uncategorized | Tags: , ,

Congratulations to Mahnush Movahedi who today just passed with distinction her dissertation defense on Efficient and Robust Distributed Computing.  Serving on her dissertation committee were Sean Luan (UNM), David Evans (UVA) and Maxwell Young (MSU).  After graduation, Mahnush will be will be moving to the University of Virginia as a postdoc to work with David Evans on Secure Computation.

It’s a great pleasure to have worked with Mahnush!  She and Mahdi will both be greatly missed in our research group.

Advertisements


Congratulations Mahdi
January 11, 2016, 8:52 pm
Filed under: Uncategorized | Tags: , ,

Congratulations to Mahdi Zamani who just passed with distinction his
dissertation defense on “Scalable and Robust Algorithms for Privacy-Preserving Applications”.  After graduation, Mahdi will be will be moving to Yale CS as a Postdoc to work with Joan Feigenbaum and Bryan Ford on the Dissent Project.  Serving on his dissertation committee were Jed Crandall, Trilce Estrada and Brian Ford(EPFL).

It’s a great pleasure to have worked with Mahdi and he’ll really be missed in both our own research group and at UNM.



The Coolest Problem You’ve Never Heard Of
April 20, 2015, 6:32 pm
Filed under: Uncategorized | Tags: , , ,

How do you compute over a noisy channel?   Say Alice and Bob want to run a distributed algorithm, but they can only communicate over a channel where each bit is flipped either stochastically or adversarially.  What is the smallest number of bits they must send in order to obtain the correct output of the algorithm, with high probability?  This general problem is called Interactive Communication, or sometimes Interactive Coding/Computation – let’s use IC for short.  It doesn’t take much imagination to think of applications of IC:  enabling sensor nodes to compute a function on their inputs in a noisy environment; designing reliable algorithms for natural algorithms [1]; and designing attack-resistant algorithms [2], just as some examples.

Wait, you may be thinking, isn’t this problem solved by error correcting codes?  No – the bits sent in the distributed algorithm may be determined only one at a time, in a dynamic manner.  Even for stochastic noise, if we naively encode each bit sent, in order to get a union bound ensuring the probability of any decoding error is small, we’ll need logarithmic blowup for each bit.  We can do better.

In fact, in the first paper on this problem, Coding for Interactive Communication, Leonard Schulman described an algorithm that requires only constant blowup, even when a constant fraction of the bits on the channel are flipped adversarially.  Schulman’s algorithm was based on a new type of code, tree codes, designed specifically for interactive communication. After this paper was published in 1996, subsequent work  focused on improving the error tolerance of Schulman’s algorithm (i.e. tolerating a larger constant fraction of errors); tuning the communication blowup to the (known) error rate; and considering the situation where the computation occurs over more than 2 parties.  See the survey paper Coding for interactive computation: progress and challenges (especially Sections 3 and 4) for details.

I’ll note here that in a sense all of information theory can be though of as a subset of IC. In particular, information theory considers “only” the class of distributed algorithms where Alice has an input that she wants to send to Bob.  In IC, we need to handle all possible distributed  algorithms, and so in a way, it’s pretty amazing that a constant adversarial noise rate can even be tolerated.

A very recent breakthrough in IC occurred in FOCS 2014, where Bernhard Haeupler in the paper Interactive Channel Capacity Revisited, made huge progress on the problem of tuning the communication blowup to a known error rate.  In particular, he described an algorithm that given a fixed and known adversarial noise rate \epsilon, achieves a communication blowup as a function of \epsilon that is conjectured to be optimal.

So what if \epsilon is not known in advance?  I’m going to end this post with a short advertisement for a recent paper with some collaborators of mine that begins to address that problem.  The paper is Interactive Communication with Unknown Noise Rate, with Varsha Dani, Mahnush Movahedi, and Maxwell Young that will be in this upcoming ICALP.  This is the first paper I’ve written about IC, and I hope it won’t be the last.  In fact, I’d like to see more people in the distributed computing community consider the problem.  In particular, it’d be nice to make progress on the (currently very hard) problem of somehow generalizing results to more than 2 parties.

[1]  For example, see this paper for a closely related problem: Breathe before Speaking: Efficient Information Dissemination Despite Noisy, Limited and Anonymous Communication

[2] This last domain is particularly interesting to me.  An obvious connection is attacks on communication channels.  A less-obvious connection is attacks on nodes.  If communication from each node is bounded, as is increasingly common for algorithms on large networks, there may be a fairly tight connection between attacks on communication channels and attacks on nodes.  Thus, there may be connections to attacks like Byzantine faults.



BDA 2014
October 22, 2014, 10:31 pm
Filed under: Uncategorized | Tags: , ,

[The following report on BDA’14 was written by my student Mahdi Zamani]

[A more polished version of this report is available HERE]

Recently, Mahnush and I attended a workshop on Biological Distributed Algorithms co-located with DISC 2014. The workshop consisted of 20 talks distributed in two days and focused on the relationships between distributed computing and distributed biological systems and in particular, on analysis and case studies that combine the two. The following is a summary of some of the talks we found interesting.

Insect Colonies and Distributed Algorithms; Insect Colony Researcher Viewpoint, Anna Dornhaus, University of Arizona

Anna talked about several open questions in modeling the behavior of different insect colonies. Insect colonies go through many changes over time in response to their changing needs and environment.

figure bda14.jpg

Figure 1. BDA 2014

Most changes happen via complex collective behaviors such as task allocation, foraging (food finding), nest building, load transport, etc. One interesting aspect of insect colonies is that unreliable individual behaviors result in complex group behaviors that are reliable. Individuals use various methods of communication such as pheromone trails, versatile signals, visual cues, substrate vibration, and waggle dance. Waggle dance is a sophisticated method of communication among honeybees to indicate resource locations by showing the angle from sun. Biologists are generally interested in computer models to know how individual behaviors impact group behaviors. In particular, they are interested to understand how positive feedbacks (a process A produces more of another process B which in turn produces more of A and so on) lead to significant consequences such as symmetry breaking. For example, ants tend to choose from one food source even if there are multiple similar sources around them. Also, larger colonies result in more symmetry breaking behavior. This motivates the following questions: How does the size of a colony affect collective behavior? Why is the workload distribution so uneven in some biological systems?

Distributed Algorithms and Biological Systems, Nancy Lynch, MIT

Nancy started by describing similarities between biological and distributed systems. Both systems often have components that perform local communications using message passing and local broadcasting. In bio systems, there are components with simple states that follow simple rules. To model a bio system using a distributed algorithm, the first step is to define the problem, the platform (physical capabilities of the system such as memory), and the strategies (rules).
Nancy then talked about two important distributed problems: leader election and maximal independent sets (MIS). In leader election, there is a ring of processes that can communicate with their neighbors and the goal is to pick a leader process. If the processes are all identical and their behaviors are deterministic, then solving this problem is impossible due to symmetry (all processes are similar). On the other hand, if the processes are not identical (i.e., each has a unique ID), then finding a leader is possible. Interestingly, in a setting with identical processes that are allowed to make random choices, this problem can be solved using a biased coin: each party flips a coin with probability 1/n to announce itself as the leader.
In MIS, the goal is to find the largest subset of the vertices of a graph such that no two neighbors (i.e., vertices connected directly via an edge) are both in the subset. There is a Las Vegas algorithm [B]  for solving this problem: in each of several rounds, each party flips a biased coin and informs its neighbors that it is in the MIS if it has not received a similar message from its neighbors. Each party stops if either it is in MIS or one of its neighbors in the MIS. Nancy finally talked about three ant colony problems that her research group has recently been working on: Ants foraging, house hunting, and task allocation.

Modeling Slime Mold Networks, Saket Navlakha, CMU

Saket started his talk by explaining an experiment related to slime mold, where the mold food was put in different locations similar to the station of the Tokyo rail system. They observed that the mold grew in a similar network as the rail system. This is very interesting because Japanese engineers could have asked a slime mold to design the rail system instead of spending several hours on the design.

Saket then continued by describing their model of the slime mold behavior for finding food sources. For simplicity, they assume there is a complete graph at first and then by calculating flow over the edges (tubes) some of the edges are disconnected. Then, they measured and compared the cost, efficiency, and fault tolerance of the network generated by their model and the Tokyo rail system: their model is as efficient as the rail system! The brain development has a similar behavior: it generates a complete neural network at first and then prunes over time. This is called the synaptic pruning algorithm.

figure slime_mold_1-660x501.jpg
Figure 2. Yellow slime mold growth
(courtesy of ScienceDaily)

The human brain starts with a very dense network of neurons and each edge keeps track of the number of times it is used to route information based on some pre-determined distribution. Then, the network is pruned based on the flow information. Saket finally talked about a similar distributed model for bacterial foraging (E. coli) in complicated terrains.

Collective Load Transport in Ants, Ofer Feinerman, Weizmann Institute

Ever seen a group of ants carrying a large foot item together? Ofer talked about collective load retrieval, the process in which a large number of ants cooperate to carry a large food item to the nest. Ofer’s research team tracked a group of ants and the load over distances of about 1000 ant lengths and used image analysis to obtain highly detailed information. They showed that the collective motion is highly cooperative and guided by temporary leaders that are knowledgeable regarding the correct direction home. Ofer finally presented a theoretical model suggesting that the ant-load system is poised at a critical point between random and ballistic motions which renders it highly susceptible to a knowledgeable leader. He played a video showing a group of ants carrying their load in a wrong direction. Then, one ant joined the group as the leader and corrected the direction.

Distributed Information Processing by Insect Societies, Stephen Pratt, Arizona State University

Stephen talked about a collective model of optimal house-hunting in rock ant Temnothorax albipennis. Each colony of T. albipennis has a single queen and hundreds of scouts (workers). In the process of house-hunting, scouts first discover new nests and assess them according to some criteria such as size and darkness. Then, they recruit other ants to the new nest using tandem running, where an informed ant leads a second ant to her destination to get a second opinion about the nest (see Figure 3↓).

Figure 3. Ants tandem run (courtesy of Stephen Pratt)

When the number of ants in the new nest reaches a threshold, scouts begin rapid transport of the rest of the colony by carrying nest-mates. In each time step, each ant is in one of these three states: explore, tandem, and transport. The transition between these states happens based on the ant’s evaluation of the quality of the nest sites and the population of the ants in this sites. Stephen defines optimality with regards to the speed and accuracy of the decision-making process. He asked: Does a colony have a greater cognitive capacity than an individual? For the house-hunting process, recent lab experiments show that when the number of nests (choices) increases, colony performs much better in choosing the good choices while lone ants visit more nests. He then asked: Do colonies make more precise discriminations than individuals? To answer this, Stephen’s team ran experiments to measure how individuals and colonies can correctly compare a dark nest with nests with various brightness levels. Interestingly, they observed that colonies can correctly choose darker nests with significantly more accuracy than individuals. They also show that even two ants perform significantly better than one.

Cells, Termites, and Robot Collectives, Radhika Nagpal, Harvard University

Radhika talked about biological systems from an engineering viewpoint. Collective behaviors often result in self-repairing and self-organizing properties which are crucial for building robust systems. In bio systems, these properties are achieved from cooperation of vast numbers of unreliable agents.

Figure 4. Termite-inspired robots
(courtesy of Harvard University)

Radhika described a bio-inspired distributed robot system that can perform group tasks such as collective construction, collective transport, and pattern/shape formation. The robots achieve a desired global goal in a completely decentralized fashion by performing local interactions with other robots. In particular, they model a large population of termites for building complex structures (see Figure 4↑).

Confidence Sharing: An Economic Strategy for Efficient Information Flows in Animal Groups, Amos Korman, CNRS and University of Paris Diderot

Amos started his talk by defining two methods of communication that exist in biological systems: passive (indirect) and active (direct) communication. Passive communication is done by transferring information with no direct intention of signaling, i.e., cues from the behavior of one animal are indirectly perceived by others. For example, it is shown that animals align their movements to those performed by their neighbors. In active communication, an animal communicates directly with others by sending parts of its internal state via, for example, pheromone trails, cell signaling, etc. Amos then continued his talk by arguing that confidence exists among animals: they are shown to become more responsive as their certainty drops. For example, crickets increase their speed when they are more confident about their intention. This confidency is propagated from one cricket to others via passive and active communication. By sharing their confidence, agents improve their unreliable individual estimates. Amos described an algorithm in which each agent compresses all information it has gathered into a single parameter that represents its confidence in its behavior. This gives a very simple and near optimal algorithm. The algorithm continuously updates agents confidence level based on the interaction it has with other agents. Unfortunately, if there are bandwidth and computational restrictions to agents, then the performance of this algorithm decreases significantly. Also, the algorithm assumes two agents who exchange confidence information must have disjoint set of exchange history.

Task Allocation in Ant Colonies, Alex Cornejo, Harvard University

Alex presented a general mathematical model for task allocation in ant colonies that can be used to achieve optimal division of labor. Based on this model, Alex described a distributed randomized efficient algorithm for task allocation that imposes minimal assumptions on the capabilities of the individual ants. The proposed algorithm requires constant amount of memory. Moreover, it assumes the ants have a primitive binary feedback function to sense the current labor allocation and to determine whether a particular task requires more workers or not. The algorithm also assumes individual workers do not differ in their ability to perform tasks. The proposed algorithm for ants converges to a near-optimal task allocation with high probability in time which is logarithmic in the size of the colony.
Compared to the previous work on task allocation, the proposed algorithm is different in the following aspects: it uses constant memory per ant, works only when the number of tasks to allocate is a small constant, and the allocation is for proportions of workers (and not for individual workers), and all workers are similar. Once workers are variant in ability to perform tasks, the task allocation problem becomes NP-hard. One drawback that was pointed out by one of the participants is that their model does not strictly adhere to the real ants’ behaviors.


Game Theory and Evolution
June 24, 2014, 8:14 pm
Filed under: Uncategorized | Tags: , , ,

The Game Theory of Life is a nice writeup of a recent PNAS paper Algorithms, Games and Evolution by Chastaina, Livnatb, Papadimitriou and Vazirani.  As a CS researcher with an amateur’s interest in biology, I really enjoyed this paper.

The paper shows a certain equivalence between two algorithms.  The first algorithm, I’ll call “evolution”.   This is an approximation (using replicator dynamics) to what happens in real Evolution in nature.  The second algorithm is the multiplicative weight update algorithm (MWUA) which we all know and love in CS.  MWUA is also known as weighted majority or winnow to many people in CS theory.

The paper proves that the outputs of “evolution” are equivalent to MWUA. They then show this implies that “evolution” is equivalent to a process that tries to maximize utility *plus* entropy (equation 3 in the paper). The utility part is not surprising since we’d certainly expect Evolution to be concerned with it.  The “plus entropy” part is surprising, and perhaps explains the surprising diversity of life.  Essentially sexual replication in the “evolution” algorithm is what gives rise to this additional entropy part.

I think it’s a pretty interesting paper. Intuitively, it proves that a simple kind of genetic algorithm (i.e. “evolution”) will give equivalent results to the MWUA (i.e. see the equivalence of Figures 1 d) and 2 d) in the paper). A nice result from the CS perspective.  However, there are a few “rah rah computer science” comments in the paper that may turn off some biologists.

I think the key thing that would really impress biologists would be making the “evolution” algorithm more realistic.  To do this would require improving Nagylaki’s theorem which is used in the paper for analyzing the “evolution” algorithm. The authors claim Nagylaki’s theorem can already be used to handle diploidy and partial recombination. Mutation is an area mentioned for future work. Modeling the interaction of organisms seems much harder. It’ll be interesting to see the followup work on this paper.

 



Latest SIGACT Distributed Computing Column
May 29, 2014, 3:04 pm
Filed under: Uncategorized | Tags: ,

The June 2014 edition of the Distributed Computing Column in SIGACT News is devoted to a review article on Transactional Memory by Gokarna Sharma and Costas Busch. An archive of the column is available online at:

https://parasol.tamu.edu/~welch/sigactNews/

Also, if you, like me, are having difficulty obtaining the full version of the March 2014 column, which reviewed a Dagstuhl seminar on Consistency in Distributed Systems by Bettina Kemme, G. Ramalingam, Andre Schiper, and Marc Shapiro, you can get it at the archive.

Enjoy!

— Jennifer Welch



Leslie Lamport Wins Turing Award
March 28, 2014, 10:40 pm
Filed under: Uncategorized | Tags: , ,

Long overdue (both the award and my reporting of it here)