For the course *Gossip and Knowledge* at ESSLLI 2022.

- 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?