đŸ± Skyspace3.0

Search

SearchSearch

2024-06-21

Aug 22, 20245 min read

random non-math stuff

I recently went to a parallel computing conference SPAA. It was a really great experience. Some of the highlights:

  • Really fancy trains / busses in France. Come on Boston, you could do better.
  • I learned that I really love theory and don’t so much love systems stuff. This was helpful for me to be reminded of.
  • Met very nice ppl, who were very enthusiastic about their research problems. This was really my favorite part. Listening to a talk I could get the basic idea, but usually 15 minutes is not actually enough for me to understand something if it’s complex and new, so I’d try to find the people that gave cool talks afterward and spend an hour or so running having them explain the problems, proofs, their feelings on the problem, what further they wish they could have done on the problem, etc.
  • cheap french bread stuff is tasty
  • Some works I found especially awesome:
  • detection in the CONGEST model (this is a distributed computation model, which will be the topic of this blog post actually once I finish this random travel description part). I just loved this one because I have thought about cycle detection a lot. And because CONGEST is cool.
  • Yi-Jun Chang et al: “Fast Broadcast in Highly Connected Networks”. This one was super cool because they took a simple textbook algorithm that looked like we had a tight analysis of, and they were like, “ah! there exist graphs where this is tight, but if we parameterize correctly then we can get a better algorithm”. Also the proof techniques were just beautiful.
  • John Kuszmaul et al: “Exponential Backoff with limited listening”. It’s a cool problem but it sounds so hard.
  • Paper: “Distributed Load Balancing in the Face of Reappearance Dependencies” (Kunal Agrawal (Washington University in St Louis); William Kuszmaul (Harvard University); Zhe Wang (FoundationDB); Jinhao Zhao (Washington University in St Louis)) This is a very neat problem and the probability analysis sounds really clever.
  • Kunal Agrawal; Benjamin Moseley, Heather Newman; Kirk Pruhs: “Scheduling Out-Trees Online to Optimize Maximum Flow” I really liked their lower bound picture. And this was a very nice problem. Cool open qs.
  • Westover, Sheffield, Kuszmaul, Farach-Colton: “A Nearly Quadratic Improvement for Memory Reallocation” These author’s chose a very interesting and simple problem and there are interesting openqs left.
  • Online Load and Graph Balancing for Random Order Inputs Sungjin Im (University of California Merced); Ravi Kumar (Google Research); Shi Li (Nanjing University); Aditya Petety (University of California Merced); Manish Purohit (Google Research) This is a very cool problem and getting tight analaysis would be epic.
  • anything distributed (MPC, congest, local, streaming)
  • it was healthy to understand a bit more the relationship between PRAM and work-span DAGs / fork-join.
  • round approximate APSP in congested clique sounds v cool.
  • sheduling via ILP was pretty cool Jansen.
  • interesting conjecture: distinguishing between one-cycle and two-cycles: conjectured to require rounds in MPC.

what I actually wanted to post about

Suppose you have a collection of machines, each with memory. You have a graph distributed amongst the machines. Specifically, each machine is given the neighbor set of one vertex in the graph. We work in the MPC model: \ There is a series of rounds, and during each round each machine can do some processing on its local memory. Then, the machines synchronously send and recieve bits of memory. We want to determine whether the graph contains a 4-cycle, while minimizing the number of rounds of computation. \

Maybe these guys will have related works? https://arxiv.org/pdf/2402.12018 Although they are working in the CONGEST model. We now give a simple algorithm for this problem.

We need the following elementary graph theory fact:

In a -free graph, for each there are at most vertices of degree .

On the first round of our algorithm we will check whether our graph violates this condition. You can do this by reporting to machine how many neighbors you have of degree . (If the machines don’t have identifiers in , then you can do some hashing trick here instead.)

Next we proceed as follows:

  • ROUND 0: send your degree to everyone in the network.
  • ROUND 1: At each vertex , for each pair , where , send the tuple to .
  • Then, each vertex checks whether it received any pair of tuples like . If so, we have found a four cycle.

LEMMA: Each vertex sends at most total messages. Proof:

  • If is a low degree vertex then it clearly sends at most messages.
  • If has degree then it sends at most messages.

LEMMA: Each vertex receives at most total messages. Proof:

  • If a vertex is low degree then each of its neighbors send it at most messages, so it gets at most total messages.
  • If a vertex is degree , then its neighbors send it at most messages, so it gets at most total messages.

Now we can detect a 4 cycle. Suppose there is a 4-cycle. Then the vertex opposite the highest degree vertex in the cycle will hear from at least two of its neighbors that there is a 2 path from to . It will conclude that there is a -cycle.

However, it’s not at all clear to me how you would extend this to ‘s.

Graph View

Backlinks

  • No backlinks found