This paper revisits a fundamental distributed computing problem in the population protocol model. Provided n agents each starting with an input color in [k], the relative majority problem asks to find the predominant color. In the population protocol model, at each time step, a scheduler selects two agents that first learn each other's states and then update their states based on what they learned.

In the well-known Minimum Linear Arrangement problem (MinLA), the goal is to arrange the nodes of an undirected graph into a permutation so that the total stretch of the edges is minimized. This paper studies an online variant of MinLA where the graph is not given at the beginning, but rather revealed piece-by-piece. The algorithm starts in a fixed initial permutation, and after a piece of the graph is revealed, the algorithm must update its current permutation to be a MinLA of the subgraph revealed so far. The objective is to minimize the total number of swaps of adjacent nodes as the algorithm updates the permutation. The main result of this paper is an online randomized algorithm that solves the online MinLA problem for the restricted cases where the graph is either a collection of cliques or a collection of lines. We show that the algorithm is$8\ ln n$- competitive, where$n$is the number of nodes of the graph. We complement this result by constructing a lower bound of$\Omega(\ln (n)$for competitiveness of any online algorithm, concluding that our randomized algorithm is asymptotically optimal.

We consider a variant of the online caching problem where the items exhibit dependencies among each other: an item can reside in the cache only if all its dependent items are also in the cache. The dependency relations can form any directed acyclic graph. These requirements arise in systems such as CacheFlow (SOSR 2016) that cache forwarding rules for packet classification in IP-based communication networks.First, we present an optimal randomized online caching algorithm which accounts for dependencies among the items. Our randomized algorithm is O(log k)-competitive, where k is the size of the cache, meaning that our algorithm never incurs the cost of O(log k) times higher than even an optimal algorithm that knows the future input sequence.Second, we consider the bypassing model, where requests can be served at a fixed price without fetching the item and its dependencies into the cache — a variant of caching with dependencies introduced by Bienkowski et al. at SPAA 2017. For this setting, we give an $O\left( {\sqrt {k \cdot \log k} } \right)$-competitive algorithm, which significantly improves the best known competitiveness. We conduct a small case study, to find out that our algorithm incurs on average 2x lower cost.