RADCON

INRIA Associate Team RADCON:
Randomized Algorithms for Distributed Computing & Networks

RADCON is a joint project between the INRIA team ASAP and the University of Calgary, Canada. RADCON was initiated in January 2013.

Objectives

Over recent years, computing systems have seen a massive increase in parallelism and inter-connectivity. Peer-to-peer systems, ad-hoc networks, sensor networks, or the “cloud” are based on highly connected and volatile networks. Individual nodes such as cell phones, desktop computers or high performance computing systems rely on parallel processing power achieved through multiple processing units. To exploit the power of massive networks or multiple processors, algorithms must cope with the scale and asynchrony of these systems, and their inherent instability, e.g., due to node, link, or processor failures. In this research project we explore randomized algorithms for large-scale networks of distributed systems, and for shared memory multi-processor systems.

For large-scale networks, decentralized gossip protocols have emerged as a standard approach to achieving fault-tolerant communication between nodes with simple and scalable algorithms. We will devise new gossip protocols for various complex distributed tasks, and we will explore the power and limits of gossip protocols in various settings.

For shared memory systems, randomized algorithms have proved extremely useful to deal with asynchrony and failures. Sometimes probabilistic algorithms provide the only solution to a problem; sometimes they are more efficient; sometimes they are simply easier to implement. We will devise efficient algorithms for some of the fundamental problems of shared memory computing, such as mutual exclusion, renaming, and consensus.

The full proposal can be found here.

Partners

Visits & Events

2015:

  • G. Giakkoupis will visit Calgary for 3 weeks in December
  • Y. Nazari visited Rennes, 1/9 — 15/12 (3.5 months)
  • G. Giakkoupis visited Calgary, 18/6 — 9/7 (3 weeks)
  • G. Giakkoupis visited Calgary, 1/3 — 8/3 (1 week)

2014:

  • G. Giakkoupis visited Calgary, 22/10 — 9/11 (2.5 weeks)
  • M. Helmi visited Rennes, 27/8 — 12/9 (2 weeks)
  • RADICON Workshop, IRISA/INRIA Rennes, 21/7 (1 day)
  • P. Woelfel visited Rennes, 20/7 — 22/7 (2 days)
  • Z. Aghazadeh visited Rennes, 20/7 — 22/7 (2 days)
  • G. Giakkoupis visited Calgary, 23/3 — 10/4 (2.5 weeks)

2013:

  • G. Giakkoupis visited Calgary, 23/11 — 14/12 (3 weeks)
  • Z. Aghazadeh visited Rennes,  7/7 — 20/7 (2 weeks)
  • P. Woelfel visited Rennes, 7/7 — 13/7 (1 week)
  • G. Giakkoupis visited Calgary, 15/4 — 7/5 (3 weeks)

Results

2015:

  • Leader election in optimal space. This is a followup of our DISC 2013 paper on the space complexity of the leader election problem in the asynchronous shared memory system with n processes. There, we had shown that O(√n) atomic registers suffice for an obstruction-free leader election algorithm. However, the best known lower bound is much smaller, namely just Ω(log n) (Styer and Peterson, 1989).  In this new work we closed the gap between the two bounds. We presented a deterministic obstruction-free implementation of a leader election object from O(log n) registers, of size O(log n) bits, thus matching the lower bound of Ω(log n). Combining our obstruction-free algorithm with techniques from previous research, we can also obtain a randomized wait-free leader election algorithm from O(log n) registers, with expected step-complexity O(log* n) against the oblivious adversary.  This work appeared in the proceedings of STOC 2015. [pdf]

2014:

  • Randomized mutual exclusion with constant amortized work. In this work we settled an open question by determining the remote memory reference (RMR) complexity of randomized mutual exclusion, on the distributed shared memory model (DSM) with atomic registers, in a weak but natural (and stronger than oblivious) adversary model. In particular, we presented a mutual exclusion algorithm that has constant expected amortized RMR complexity and is deterministically deadlock free. Prior to this work, no randomized algorithm with o(log n/loglog n) RMR complexity was known for the DSM model. Our algorithm is fairly simple, and compares favorably with one by Bender and Gilbert (FOCS 2011) for the CC model, which has expected amortized RMR complexity O(log2 log n) and provides only probabilistic deadlock freedom. This work appeared in the proceedings of FOCS 2014. [pdf]

2013:

  • Gossip protocols for renaming and sorting. We devised efficient gossip-based protocols for some fundamental distributed tasks. The protocols assume an n-node network supporting point-to-point communication, and in every round, each node exchanges information of size O(log n) bits with (at most) one other node. We first considered the renaming problem, that is, to assign distinct IDs from a small ID space to all nodes of the network. We proposed a renaming protocol that divides the ID space among nodes using a natural push or pull approach, achieving logarithmic round complexity with ID space {1,…,(1+ε) n}, for any fixed ε >0. A variant of this protocol solves the tight renaming problem, where each node obtains a unique ID in {1,…,n}, in O(log2 n) rounds. Next we studied the following sorting problem. Nodes have consecutive IDs 1 up to n, and they receive numerical values as inputs. They then have to exchange those inputs so that in the end the input of rank k is located at the node with ID k. Jelasity and Kermarrec (2006) suggested a simple and natural protocol, where nodes exchange values with peers chosen uniformly at random, but it is not hard to see that this protocol requires Ω(n) rounds. We proved that the same protocol works in O(log2 n) rounds if peers are chosen according to a non-uniform power law distribution. This work appeared in the proceedings of DISC 2013. [pdf]
  • Space efficient leader election. We proposed a deterministic obstruction-free implementation of leader election from O(√n) atomic registers in the standard asynchronous shared memory system with n processes. We provided also a technique to transform any deterministic obstruction-free algorithm, in which any process can finish if it runs for b steps without interference, into a randomized wait-free algorithm for the oblivious adversary, in which the expected step complexity is polynomial in n and b. This transformation allows us to combine our obstruction-free algorithm with the leader election algorithm by Giakkoupis and Woelfel (2012), to obtain a fast randomized leader election (and thus test-and-set) implementation from O(√n) registers, that has expected step complexity O(log* n) against the oblivious adversary. Our algorithm provides the first sub-linear space upper bound for obstruction-free leader election. A lower bound of Ω(log n) has been known since 1989. Our research is also motivated by the long-standing open problem whether there is an obstruction-free consensus algorithm which uses fewer than n registers. This work appeared in the proceedings of DISC 2013. [pdf]
  • Randomized loose renaming algorithms. Renaming is a classic distributed coordination task in which a set of processes must pick distinct identifiers from a small namespace. We studied the time complexity of this problem when the namespace is linear in the number of participants, a variant known as loose renaming. We gave a non-adaptive algorithm with O(loglog n) (individual) step complexity, where n is a known upper bound on contention, and an adaptive algorithm with step complexity O((loglog k)2), where k is the actual contention in the execution. We also presented a variant of the adaptive algorithm which requires O(k loglog k) total process steps. All upper bounds hold with high probability against a strong adaptive adversary. We complemented our algorithms with an Ω(loglog n) expected time lower bound on the complexity of randomized renaming using test-and-set operations and linear space. The result is based on a new coupling technique, and is the first to apply to non-adaptive randomized renaming. Since our algorithms use O(n) test-and-set objects, our results provide matching bounds on the cost of loose renaming in this setting. This work appeared in the proceedings of PODC 2013. [pdf]

Publications

2015:

  • G. Giakkoupis (INRIA), M. Helmi (UofC), L. Higham (UofC), and P. Woelfel (UofC).
    Test-and-Set in optimal space.
    Proc. 47th ACM Symposium on Theory of Computing (STOC), pp. 615-623, Jun. 14-17 2015.
    [pdf]

2014:

  • G. Giakkoupis (INRIA) and P. Woelfel (UofC).
    Randomized mutual exclusion with constant amortized RMR complexity on the DSM.
    Proc. 55th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 504-513, Oct. 18-21 2014.
    [pdf]

2013:

  • G. Giakkoupis (INRIA), A-M. Kermarrec (INRIA), and P. Woelfel (UofC).
    Gossip protocols for renaming and sorting.
    Proc. 27th International Symposium on Distributed Computing (DISC), pp. 194-208, Oct. 14-18 2013.
    Journal version invited to Distributed Computing, DISC 2013 Special Issue.
    [pdf] [interview]
  • G. Giakkoupis (INRIA), M. Helmi (UofC), L. Higham (UofC), and P. Woelfel (UofC).
    An O(sqrt n) space bound for obstruction-free leader election.
    Proc. 27th International Symposium on Distributed Computing (DISC), pp. 46-60, Oct. 14-18 2013.
    Journal version invited to Distributed Computing, DISC 2013 Special Issue.
    [pdf] [interview]
  • D. Alistarh (MIT), J. Aspnes (Yale), G. Giakkoupis (INRIA), and P. Woelfel (UofC).
    Randomized loose renaming in O(loglog n) time.
    Proc. 32nd ACM Symposium on Principles of Distributed Computing (PODC), pp. 200-209, Jul. 22-24 2013.
    [pdf]