Exercises | Gossip and Knowledge

Monday

With pen an paper, draw an initial total gossip graph for 4 agents, and execute the call sequence ab;bc;cd;da. Draw a new graph after each call, such that you have five graphs with four calls between them.
Open ElmGossip and check your drawings by executing the same call sequence there, step by step. Note that you will first have to enter Abcd aBcd abCd abcD for the initial graph.
Is the sequence ab;bc;cd;da allowed according to the ANY, the LNS and the CMO protocols?
Find a call sequence that is permitted for CMO but not for LNS.
Find a (non-total) gossip graph where CMO is weakly successful, but LNS is unsuccessful.
Define your own protocol in ElmGossip which allows more calls than LNS, but fewer than CMO.
Consider the "Spider" protocol. Why does the protocol condition use σˣ=ϵ and not σ=ϵ?

Do the same exercises as yesterday, but then using GoMoChe instead of ElmGossip.
Assume synchronous semantics and a total initial graph for four agents. Given the actual call sequence ab;cd;ac;bd, which other call sequences does agent a consider possible? Does your answer differ for when ANY or LNS is common knowledge? Compute the answers manually, then check them using GoMoChe.
Come up with variants of the four questions from the lecture today.
Let's break the rules! Suppose we are allowed to use the K^P operator in the protocol condition P_ab for the very same protocol P. Why is this dangerous? Can you define Russel's protocol, i.e.\ a protocol that allows a call if and only if it does not allow it? (For a hint, read the HTML source of this page.)

Can a graph be a sun graph and a (double) bush at the same time?
Consider the "ring" example for dynamic gossip with five agents shown in the lecture. Check that ab;de;bc;ec;db;ac is actually successful. Now consider a ring which only has neighbour-edges in one direction. Note that the same sequence no longer works. Why? Can you still find a successful sequence of six calls?
Use the pdfTreeWith function to create execution trees with or without indistinguishability relations. How many agents, relations and calls can you have until the graphs become unreadable?
(BIG question, programming needed!) Extend ElmGossip or GoMoChe by writing an Elm or Haskell function to check whether a graph is a (double) bush. Send it to Malvin or make a pull request ;-)

Consider the "diamond without arms" example from the lecture. Can you find an LNS-strengthening that is strongly successful on it?
Can you formally define a strengthening or weakening of LNS that is better in general? Idea: If we know that LNS is strongly successful, let's do it, otherwise, do LNS calls as long as possible, and after that switch to CO. What would be your suggestion for a good protocol with such fallbacks? Can you use GoMoChe to check whether it beats LNS and its strengthenings in the sense of reaching strong success on more graphs?

Where does weak CO fit into the inclusion hierarchy of reachable distributions? (Thank you to the audience member who suggested this!)
Check that the proof for "everything is subreachable" can indeed be adjusted to "everything is P-subreachable" where P is any among the five mentioned protocols.
Why is the expected execution length of ANY not infinite?