一个算法问题

[oxogenesis]

不要改题目，能回答的回答

问题描述：

固定数量的客户端连接同一服务器
服务器不具备数据存储功能，只有单条消息定向转发功能
客户端之间借助服务器数据中继传播消息

每个客户端具有唯一编号
发送的每条消息有编号，从 1 开始，依次加 1，并且都带有时间戳
比如：
客户端 A 发的消息是 A1，A2，A3...
客户端 B 发的消息是 B1，B2，B3...
...

客户端可以保存自己生成的消息和收到的消息
客户端不能伪造其他客户端的消息
客户端可以转发其他客户端的消息，举例：
A 可以向 C 转发消息 B2

客户端知道所有其他客户端的编号
客户端并不保证总是在线
在一个时刻，有可能全都在线，有可能都不在线，有可能部分在线

如何用最少的消息，使得每一个客户端都尽可能获得全部客户端的消息

[oxogenesis]

来个大佬大神，回答回答，谢谢！

实在不行改问题歪楼也行啊，捧个人场

消灭零回复

[12tall]

前排插眼，学习经验

[mengzhuo]

经典的区块链，不用我多说了吧

[arrow8899]

最后一句没看明白

[a7a2a7a2]

貌似考这个是不是：
1、基于原始客户端可信度最高设计，cdn，可去中心化动态服务（原始掉线后从其他服务器获取，基于最后时间戳可信度最高）
2、基于消息发出即不可修改设计,类似区块连

[oxogenesis]

@mengzhuo 用
@arrow8899 举例说明
客户端 A、B、C...不断的再发消息 A1~An、B1~Bm、C1~Cx...

如果所有客户端都在线，一个客户端生成一条消息，可以向其他客户端各发一条消息
如果有客户端下线一段时间，然后再上线，如何将离线这段时间内的所有消息全部同步回来？
先得找一下谁在线，然后告诉对方自己最后收到的消息，对方给你同步后续消息，但是对方也有可能是刚刚上线，对方消息就不全

[mengzhuo]

@oxogenesis 你乱想的太多了，看下区块链的介绍你就明白怎么搞了。

[oxogenesis]

@a7a2a7a2 一个算法的问题，不是考题
自己弄得个聊天程序，借用区块链思想，现在在想群聊的实现方法
目前初步拟定群控制消息，群消息格式
https://github.com/oxogenesis/oxo-chat-client/blob/master/src/utils/json_schema.js#L225

[a7a2a7a2]

@oxogenesis 如我回复的第二条，那就是区块连的话，很简单。
消息不全也要先同步最大数量的

任何刚上线的的客户端都要请求一次所有编号内的客户端的最后一条消息，等所有客户端返回他们最后一条消息的编号，取最大编号，然后对比自己的存储的该客户端唯一编号最大消息编号就能知道少了多少，然后直接从刚才返回最大消息编号的服务区同步没有的数据。

每当收到最新在线客户端发来消息的编号跟自己存储的编号不连续的时候就需要触发同步服务。

看我上面的 2 个设计，你需要的是什么
@oxogenesis

[oxogenesis]

这里的问题是不是所有客户端都在线

请求所有客户端，对方不一定在线，那就需要有重试机制，可能有的客户端说完话后就长时间不在线

等待某个客户端发消息（这个触发机制肯定是要的），可能有的客户端说完话后，长时间不发言

我倾向于，上线以后，靠在线的部分客户端，尽可能多的同步当前在线客户端的所有数据，再加上被动触发机制、引用关联机制、适当强度的轮询机制，消息类型要少，消息请求响应数量要少，降低系统复杂度和服务器的负载

[wutiantong]

这是基于 BLE/WiFi-Direct 的 Local Chat 么？

[oxogenesis]

@wutiantong 不是，还是需要服务器的，但是服务器只做消息转发，不存储数据，所有数据都存在个人计算设备

[fluorinedog]

写个 Gossip 协议吧。
看起来服务器只需要保存账号->ip 的映射，其他都靠 P2P （暂时不考虑穿透）。信息转发靠洪泛。
不过，如果楼主不在服务器上放数据的话，完全无法实现离线留言功能啊。A 上线给 B 发消息=>A 下线=>B 上线

[w516322644]

MQTT ？

[wutiantong]

@oxogenesis 客户端发的这些消息是广播（ to all ），还是私聊（ to peer ），还是兼而有之呢？
题目前半段的描述感觉像是广播，但又忽然提到了转发（ A 向 C 转发 B2 ），这又是属于私聊的性质了。

[IanPeverell]

Gossip 协议；轮询附近节点最近消息时间戳并发送本地最新消息时间戳，如果接受者本地最新消息时间戳比询问者时间戳晚则发送询问者缺失时间段消息，否则不做处理
基本思想就是把 Bitcoin 的 height 换成时间戳

[oxogenesis]

@fluorinedog 对，私聊的话，得两个人同时在线，群聊只要有一个人在线，就相当于给所有后上线的人做种子了
服务器什么都不能存，要断绝对任何服务器的依赖，服务器只形式路由器的职能
这样才能保证，客户端对数据的完全控制
可以承受牺牲部分可靠性、便利性，
现在网络这么发达，如果个体愿意，保持持续在线并不难

[oxogenesis]

@wutiantong 所有的消息都是一个客户端通过服务器发送给另一个客户端，通过多条消息来实现“广播的效果”

私聊（已经实现客户端到客户端加密），并且密钥隔一段时间换一次
群聊的想法是，每个群里的任意两个客户端协商一次密钥，以后都用这个密钥来加密，群聊就是把同一句话用不同的密钥加密后发个对应的客户端

[oxogenesis]

@IanPeverell
我的想法还停留在，不依赖特定服务器，将服务器降维到网络设备。
而不是完全的 p2p，感觉 p2p 的服务质量不太靠谱

[no1xsyzy]

如果说 A 向 B 发送消息，结果 B 突然变得暂时不可及（比如 B 连续宣称包完整性检验失败），那么这时候会发生什么？
1. 服务器留存并等待 B 再次可及；
2. 丢弃；
3. 服务器将 “不可及” 这一结果返回给 A，由 A 来决定如何处理。

根据你的 spec，1 不被允许。剩下的，2 就是 UDP，3 就是 TCP。把服务器等价成 ARP，允许任何一台机器成为网关和边际网关就行。
然后在这之上建立一个 P2P 聊天系统。那么就可以抄答案了。
现在你还有什么问题吗？